𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On complete subgraphs of color-critical graphs

✍ Scribed by Xiang-Ying Su

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
488 KB
Volume
143
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is called k-critical if x(G) = k and x(G -e) -C x(G) for each edge e of G, where x denotes the chromatic number. T. Gallai conjectured that every k-critical graph of order n contains at most n complete (kl)-subgraphs. In 1987, Stiebitz proved Gallai's conjecture in the case k = 4, and in 1992 Abbott and Zhou proved Gallai's conjecture for all k > 5. In their paper, Abbott and Zhou asked the following question: is it true that the number of complete (k -1)-subgraphs of any k-critical graph G of order n > k is at most n -k + 3 (k > 5)? In this paper, we give a positive answer to the question above for the cases k = 5,6.

📜 SIMILAR VOLUMES

On a conjecture of Gallai concerning com
On a conjecture of Gallai concerning complete subgraphs of k-critical graphs
✍ H.L. Abbott; B. Zhou 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 418 KB

Abbott, H.L. and B. Zhou, On a conjecture of Gallai concerning complete subgraphs of k-critical graphs, Discrete Mathematics 100 (1992) 223-228. A graph G is said to be k-critical if it has chromatic number k but every proper subgraph of G has a (k -l)-coloring. T. Gallai asked whether each k-criti

Subgraph-avoiding coloring of graphs
Subgraph-avoiding coloring of graphs
✍ Jia Shen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract Given a “forbidden graph” __F__ and an integer __k__, an __F‐avoiding k‐coloring__ of a graph __G__ is a __k__‐coloring of the vertices of __G__ such that no maximal __F__‐free subgraph of __G__ is monochromatic. The __F‐avoiding chromatic number__ __ac__~__F__~(__G__) is the smallest i

Color-Critical Graphs on a Fixed Surface
Color-Critical Graphs on a Fixed Surface
✍ Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 420 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let S be an orientable surface other than the sphere and let k be a natural number. Then there are infinitely many k-color-critical graphs on S if and only if 3 k 5. In particular, if k 5, then there exists a polynomially

Complete subgraphs of the graphs of conv
Complete subgraphs of the graphs of convex polytopes
✍ S. Gallivan; E.R. Lockeberg; P. McMullen 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 631 KB

It is shown that if three vertices of the graph c?(l)) of a convex 3-polytope P are chosen, then G(P) contains a refinement of the complete graph C,, on four vertices, for which the three chosen vertices are principal (that is, correspond to vertices of C, in the refinement.. In general, all four ve