Hajós' graph-coloring conjecture: Variations and counterexamples

1979/04/01 by Paul A. Catlin, Paul A Catlin · 103 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Conjecture #Counterexample #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph factorization #Graph power #Line graph #Mathematics #graph theory and CDMA systems

paper · doi:10.1016/0095-8956(79)90062-5

published in Journal of Combinatorial Theory, Series B 26(2), 268-274 (Elsevier BV)

crossref issued 1979/04/01 · crossref published 1979/04/01 · crossref published-print 1979/04/01 · openalex publication_date 1979/04/01 · crossref created 2005/02/09 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23 · crossref indexed 2026/08/05

Cited by

• Reducing Hajós' 4-coloring conjecture to 4-connected graphs
• Any 7-Chromatic Graphs Has K 7 Or K 4,4 As A Minor
• On topological graphs with at most four crossings per edge
• Hadwiger's Conjecture is True for Almost Every Graph
• Graph Minors. XIX. Well-quasi-ordering on a surface
• Albertson conjecture [wikipedia]
• Hadwiger conjecture (graph theory) [wikipedia]