## Keywords

graph theory, graph minors, graph coloring, Hadwiger's conjecture

## Abstract

Hadwiger's Conjecture from 1943 states that every graph with no K_{t} minor is (t-1)-colorable; it remains wide open for t ≥ 7. For positive integers t and s, let K_{t}^{-s} denote the family of graphs obtained from the complete graph K_{t} by removing s edges. We say that a graph has no K_{t}^{-s} minor if it has no H minor for every H in K_{t}^{-s}. In 1971, Jakobsen proved that every graph with no K_{7}-^{2} minor is 6-colorable. In this dissertation, we first study the extremal functions for K_{8}^{-4} minors, K_{9}^{-6} minors, and K_{10}^{-12} minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K_{8}^{-4} minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K_{9}^{-6} minor, and every graph on n ≥ 10 vertices with at least 5.5n-17.5 edges has a K_{10}^{-12} minor. We then prove that every graph with no K_{8}^{-4} minor is 7-colorable, every graph with no K_{9}^{-6} minor is 8-colorable, and every graph with no K_{10}^{-12} minor is 9-colorable. The proofs use the extremal functions as well as generalized Kempe chains of contraction-critical graphs obtained by Rolek and Song and a method for finding minors from three different clique subgraphs, originally developed by Robertson, Seymour, and Thomas in 1993 to prove Hadwiger's Conjecture for t = 6. Our main results imply that H-Hadwiger's Conjecture is true for each graph H on 8 vertices that is a subgraph of every graph in K_{8}^{-4}, each graph H on 9 vertices that is a subgraph of every graph in K_{9}^{-6}, and each graph H on 10 vertices that is a subgraph of every graph in K_{10}^{-12}.

## Completion Date

2023

## Semester

Fall

## Committee Chair

Song, Zixia

## Degree

Doctor of Philosophy (Ph.D.)

## College

College of Sciences

## Department

Mathematics

## Degree Program

Mathematics

## Format

application/pdf

## Identifier

DP0028050

## URL

https://purls.library.ucf.edu/go/DP0028050

## Language

English

## Release Date

December 2024

## Length of Campus-only Access

1 year

## Access Status

Doctoral Dissertation (Campus-only Access)

## Campus Location

Orlando (Main) Campus

## STARS Citation

Lafferty, Michael M., "Extremal Functions for Kt-s Minors and Coloring Graphs with No Kt-s Minors" (2023). *Graduate Thesis and Dissertation 2023-2024*. 66.

https://stars.library.ucf.edu/etd2023/66

Restricted to the UCF community until **December 2024**; it will then be open access.