𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture of Gallai concerning complete subgraphs of k-critical graphs

✍ Scribed by H.L. Abbott; B. Zhou

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
418 KB
Volume
100
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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-critical graph of order n contains at most n complete subgraphs of order k -1. This is clearly so when k = n, and it is also true when k = 3 since the only 3-critical graphs are the cycles of odd length. M. Stiebitz recently gave a positive answer to Gallai's question in the case k = 4. In this paper we give an affirmative answer for all k 3 5.

📜 SIMILAR VOLUMES

On complete subgraphs of color-critical
On complete subgraphs of color-critical graphs
✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 488 KB

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 1

On a conjecture of Thomassen concerning
On a conjecture of Thomassen concerning subgraphs of large girth
✍ Domingos Dellamonica Jr; Václav Koubek; Daniel M. Martin; Vojtěch Rödl 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

In 1983 C. Thomassen conjectured that for every k, g ∈ N there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kühn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based

Proof of Mader's conjecture on k-critica
Proof of Mader's conjecture on k-critical n-connected graphs
✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley

Proof of a Conjecture of Mader, Erdös an
Proof of a Conjecture of Mader, Erdös and Hajnal on Topological Complete Subgraphs
✍ B. Bollobás; A. Thomason 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 89 KB

We show that every graph G of size at least 256 p 2 |G| contains a topological complete subgraph of order p. This slight improvement of a recent result of Komlós and Szemerédi proves a conjecture made by Mader and by Erdös and Hajnal.