Hadwiger's conjecture for graphs with infinite chromatic number

2012/12/13 by Dominic van der Zypen, van der Zypen, Dominic · 1 citation
Computer Science · Mathematics · #05C15 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1212.3093

openalex publication_date 2012/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct a connected graph H such that (1) χ(H) = ω; (2) K_ω, the complete graph on ωpoints, is not a minor of H. Therefore Hadwiger's conjecture does not hold for graphs with infinite coloring number.

Cited by

• Hadwiger's conjecture for hypergraphs

Related

• Hadwiger's conjecture for hypergraphs
• A weak form of Hadwiger's conjecture
• Hadwiger's Conjecture for some graphs with independence number two
• Hadwiger's conjecture: finite vs infinite graphs
• Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2