On complete subgraphs of color-critical graphs

DOI10.1016/0012-365X(94)00017-DMaRDI QIDQ1897440zbMATH OpenFDO

Authors Xiang-Ying Su

Publication date 11 March 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00017-D

zbMATH Keywords

\(k\)-critical graphchromatic numbercolor-critical graphscomplete subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

A graph \(G\) is called \(k\)-critical if \(\chi(G)= k\) and \(\chi(G- e)= k- 1\) for each edge \(e\) of \(G\), where \(\chi\) denotes the chromatic number. The author proves for \(4\leq k\leq 6\) that any \(k\)-critical graph \(G\) of order greater than \(k\) has an edge that is contained in at most one complete \((k-1)\)-subgraph of \(G\). From this it follows that the number of complete \((k- 1)\)-subgraphs of any \(k\)-critical graph \(G\) of order \(n> k\) is at most \(n- k+ 3\) for \(4\leq k\leq 6\).

Recommendations

• scientific article; zbMATH DE number 798654
• Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs
• Colour-critical graphs with few edges
• On the number of edges in colour-critical graphs and hypergraphs
• On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs

Cites work

• Hajos' graph-coloring conjecture: Variations and counterexamples
• On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs
• On critical subgraphs of colour-critical graphs
• Subgraphs of colour-critical graphs

Cited in

(23)

• On list critical graphs
• On color critical graphs
• Independent sets in k-chromatic graphs
• Subgraphs of colour-critical graphs
• On constructive methods in the theory of colour-critical graphs
• On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs
• On extensions of a conjecture of Gallai
• Generalizations of independence and chromatic numbers of a graph
• Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs
• Counting substructures. I: Color critical graphs
• Questions on color-critical subgraphs
• Graphs with large maximum degree containing no edge-critical graphs
• Construction of Colour-Critical Graphs With Given Major-Vertex Subgraph
• scientific article; zbMATH DE number 3891399 (Why is no real title available?)
• scientific article; zbMATH DE number 4160758 (Why is no real title available?)
• scientific article; zbMATH DE number 3957142 (Why is no real title available?)
• scientific article; zbMATH DE number 4043873 (Why is no real title available?)
• scientific article; zbMATH DE number 3520443 (Why is no real title available?)
• Edge-critical \(G,H\) colorings.
• scientific article; zbMATH DE number 1923176 (Why is no real title available?)
• scientific article; zbMATH DE number 750697 (Why is no real title available?)
• scientific article; zbMATH DE number 798654 (Why is no real title available?)
• On the maximum number of edges in k-critical graphs

This page was built for publication: On complete subgraphs of color-critical graphs

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