𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On color critical graphs

✍ Scribed by Vojtech Rödl; Zsolt Tuza

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
555 KB
Volume
38
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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 generalized graph colorings
On generalized graph colorings
✍ Jason I. Brown; Derek G. Corneil 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

Given a property P, graph G. and k 2 0, a P k-coloring is a function 7r: V(G) + { I , ... , k) such that the subgraph induced by each color class has property P; x ( G : P ) is the least k, for which G has a P k-coloring. We investigate here the theory of P colorings. Generalizations of the wellknow