-critical graphs with small high vertex cliques

DOI10.1016/J.JCTB.2011.05.003zbMATH Open1241.05036arXiv1102.1023OpenAlexW2024339209MaRDI QIDQ765195FDOQ765195

Authors: Landon Rabern 

Publication date: 19 March 2012

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

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.

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

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

zbMATH Keywords

graph coloringBrooks' theorem

Mathematics Subject Classification ID

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

Cites Work

• Ore-type versions of Brooks' theorem
• Title not available (Why is that?)

Cited In (9)

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

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)