Hadwiger's conjecture for graphs with forbidden holes

2016/07/22 by Song, Zi-Xia, Thomas, Brian · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.06718

Abstract

Given a graph G, the Hadwiger number of G, denoted by h(G), is the largest integer k such that G contains the complete graph K_k as a minor. A hole in G is an induced cycle of length at least four. Hadwiger's Conjecture from 1943 states that for every graph G, h(G)≥ χ(G), where χ(G) denotes the chromatic number of G. In this paper we establish more evidence for Hadwiger's conjecture by showing that if a graph G with independence number α(G)≥3 has no hole of length between 4 and 2α(G)-1, then h(G)≥χ(G). We also prove that if a graph G with independence number α(G)≥2 has no hole of length between 4 and 2α(G), then G contains an odd clique minor of size χ(G), that is, such a graph G satisfies the odd Hadwiger's conjecture.

Cited by

• Dominating Hadwiger's Conjecture holds for all 2K₂-free graphs

Related

• Hadwiger's Conjecture for some graphs with independence number two
• A note on Hadwiger's Conjecture for W₅-free graphs with independence\n number two
• Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2
• Clique minors in graphs with a forbidden subgraph
• Hadwiger's conjecture for hypergraphs