Keywords

graph theory; Hadwiger's Conjecture; graph minors; Dominating clique minors; graph coloring

Abstract

A dominating Kt minor in a graph 𝐺 is a sequence (𝑇1,…,𝑇t) of pairwise disjoint non-empty connected subgraphs of 𝐺, such that for 1≤𝑖< 𝑗≤𝑡, every vertex in 𝑇j has a neighbor in 𝑇i. Replacing “every vertex in 𝑇j” by “some vertex in 𝑇j” retrieves the standard definition of a 𝐾t minor. The strengthened notion was introduced by Illingworth and Wood in 2024, who asked whether every graph with chromatic number 𝑡 contains a dominating 𝐾t minor. This is a substantial strengthening of the celebrated Hadwiger’s Conjecture, which asserts that every graph with chromatic number 𝑡 contains a 𝐾t minor. At the “New Perspectives in Colouring and Structure” workshop held at the Banff International Research Station from September 29 - October 4, 2024, Norin referred to this question as the “Dominating Hadwiger’s Conjecture” and believes it is likely false. In this paper we prove that the Dominating Hadwiger’s Conjecture holds for all 2K2-free graphs. A key component of our proof is the use of the existence of an induced banner, obtained by adding a vertex adjacent to exactly one vertex on a cycle of length four. This work was supported by NSF grant DMS-2153945 supplemental funding for undergraduate students at the University of Central Florida.

Thesis Completion Year

2026

Thesis Completion Semester

Spring

Thesis Chair

Song, Zi-Xia

College

College of Sciences

Department

School of Data, Mathematical, and Statistical Sciences

Thesis Discipline

Mathematics

Language

English

Access Status

Open Access

Length of Campus Access

None

Campus Location

Orlando (Main) Campus

Download

Share

COinS
 

Accessibility Statement

This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.