A density bound for triangle‐free 4‐critical graphs

DOI10.1002/jgt.22904zbMath1525.05053arXiv2012.01503OpenAlexW3107865975MaRDI QIDQ6047637

Benjamin Moore, Evelyne Smith-Roberge

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.01503

zbMATH Keywords

graph colouringtriangle-free graphspotential methodfour-critical graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Characterizing 4-critical graphs with Ore-degree at most seven
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• A Brooks-type result for sparse critical graphs
• Three-coloring Klein bottle graphs of girth five
• On the density of \(C_7\)-critical graphs
• On the minimum number of edges in triangle-free 5-critical graphs
• Coloring graphs with fixed genus and girth
• On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
• 4-chromatic projective graphs
• Sparse Graphs Are Near-Bipartite