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

DOI10.1016/J.JCTB.2017.09.010zbMATH Open1379.05041arXiv1409.5116OpenAlexW2962723552MaRDI QIDQ684124FDOQ684124

Luke Postle

Publication date: 9 February 2018

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

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.

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

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

zbMATH Keywords

graph coloringpotential methodOre-degree4-critical graphs

Mathematics Subject Classification ID

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

Cites Work

• Ore-type versions of Brooks' theorem
• Title not available (Why is that?)
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Title not available (Why is that?)
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• A Brooks-type result for sparse critical graphs
• Graphs with chromatic number close to maximum degree
• Title not available (Why is that?)
• The Colouring of Maps

Cited In (2)

• Critical graphs for the chromatic edge-stability number
• 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)