Some remarks on Hajós' conjecture

DOI10.1016/j.jctb.2004.08.005zbMath1061.05040OpenAlexW4210426162MaRDI QIDQ707025

Carsten Thomassen

Publication date: 9 February 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2004.08.005

zbMATH Keywords

chromatic numbersubdivisionsHajós' conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Perfect graphs (05C17)

Related Items (20)

Coloring immersion-free graphs ⋮ Hadwiger's conjecture for powers of cycles and their complements ⋮ Clustered variants of Hajós' conjecture ⋮ Wheels in planar graphs and Hajós graphs ⋮ 4‐Separations in Hajós graphs ⋮ Hadwiger's Conjecture for the Complements of Kneser Graphs ⋮ Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz ⋮ Chromatic number and complete graph substructures for degree sequences ⋮ Hadwiger's conjecture for inflations of 3-chromatic graphs ⋮ Hadwiger's conjecture and inflations of the Petersen graph ⋮ Hajós' conjecture and cycle power graphs ⋮ The thickness and chromatic number of \(r\)-inflated graphs ⋮ On topological relaxations of chromatic conjectures ⋮ Reducing Hajós' 4-coloring conjecture to 4-connected graphs ⋮ Five-coloring graphs on the Klein bottle ⋮ Partitioning a graph into convex sets ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Dichromatic number and forced subdivisions ⋮ The Kelmans-Seymour conjecture. IV: A proof ⋮ Rooted topological minors on four vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• The strong perfect graph theorem
• Hadwiger's conjecture is true for almost every graph
• A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\)
• On critical graphs with chromatic index 4
• Hajos' graph-coloring conjecture: Variations and counterexamples
• \(3n-5\) edges do force a subdivision of \(K_5\)
• Five-coloring graphs on the torus
• Explicit Ramsey graphs and orthonormal labelings
• Color-critical graphs on a fixed surface
• Topological minors in graphs of large girth
• On the conjecture of Hajos
• On some extremal problems in graph theory
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Graph Theory and Probability. II
• On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation
• Extremal bipartite subgraphs of cubic triangle-free graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Some remarks on the theory of graphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Some remarks on Hajós' conjecture