-critical graphs with small high vertex cliques

DOI10.1016/J.JCTB.2011.05.003MaRDI QIDQ765195zbMATH OpenOpenAlexFDO

Authors Landon Rabern

Publication date 19 March 2012

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

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

zbMATH Keywords

Brooks' theoremgraph coloring

Mathematics Subject Classification ID

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

Abstract: We prove that $K_{chi(G)}$ is the only critical graph $G$ with $chi(G)geqDelta(G)geq6$ and $omega(mathcalH(G))leqleftlfloorfracDelta(G)2ightfloor-2$. Here $mathcalH(G)$ is the subgraph of $G$ induced on the vertices of degree at least $chi(G)$. Setting $omega(mathcalH(G))=1$ proves a conjecture of Kierstead and Kostochka.

Recommendations

• Partitioning and coloring graphs with degree constraints
• Graphs with \(\chi=\Delta\) have big cliques
• On the \(\Delta\)-subgraph of graphs which are critical with respect to the chromatic index
• scientific article; zbMATH DE number 3957142
• A note on Vizing's independence number conjecture of edge chromatic critical graphs

Cites work

• scientific article; zbMATH DE number 3851121 (Why is no real title available?)
• Ore-type versions of Brooks' theorem

Cited in

(9)

• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• Partitioning and coloring graphs with degree constraints
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• Graphs with \(\chi=\Delta\) have big cliques
• Graphs with chromatic number close to maximum degree
• scientific article; zbMATH DE number 7641240 (Why is no real title available?)
• A note on \(\Delta\)-critical graphs
• Special issue in honour of Landon Rabern
• Partitioning of a graph into induced subgraphs not containing prescribed cliques

This page was built for publication: \(\Delta \)-critical graphs with small high vertex cliques

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