Characterizing 4-critical graphs with Ore-degree at most seven

DOI10.1016/J.JCTB.2017.09.010MaRDI QIDQ684124zbMATH OpenOpenAlexFDO

Authors Luke Postle

Publication date 9 February 2018

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

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

zbMATH Keywords

graph coloringpotential methodOre-degree4-critical graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Abstract: Dirac introduced the notion of a k-critical graph, a graph that is not (k-1)-colorable but whose every proper subgraph is (k-1)-colorable. Brook's Theorem states that every graph with maximum degree k is k-colorable unless it contains a subgraph isomorphic to K_{k+1} (or an odd cycle for k=2). Equivalently, for all k>=4, the only k-critical graph of maximum degree k-1 is K_k. A natural generalization of Brook's theorem is to consider the Ore-degree of a graph, which is the maximum of d(u)+d(v) over all edges uv. Kierstead and Kostochka proved that for all k>=6 the only k-critical graph with Ore-degree at most 2k-1 is K_k. Kostochka, Rabern and Steibitz proved that the only 5-critical graphs with Ore-degree at most 9 are K_5 and a graph they called O_5. A different generalization of Brook's theorem, motivated by Hajos' construction, is Gallai's conjectured bound on the minimum density of a k-critical graph. Recently, Kostochka and Yancey proved Gallai's conjecture. Their proof for k>=5 implies the above results on Ore-degree. However, the case for k=4 remains open, which is the subject of this paper. Kostochka and Yancey's short but beautiful proof for the case k=4 says that if $G$ is a $4$-critical graph, then |E(G)|>= (5|V(G)|-2)/3. We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G, then |E(G)|>= 1.6 |V(G)| + .2 alpha(D_3(G)) - .6, where D_3(G) is the graph induced by the degree three vertices of G. As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K_4 and Ore compositions.

Recommendations

• Ore's conjecture on color-critical graphs is almost true
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Structure in sparse \(k\)-critical graphs
• On the edge-density of 4-critical graphs
• Colour-critical graphs with few edges

Cites work

• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Graphs with chromatic number close to maximum degree
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Ore-type versions of Brooks' theorem
• The Colouring of Maps

Cited in

(4)

• Critical graphs for the chromatic edge-stability number
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Structure in sparse \(k\)-critical graphs
• A density bound for triangle‐free 4‐critical graphs

This page was built for publication: Characterizing 4-critical graphs with Ore-degree at most seven

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684124)