✦ LIBER ✦

Decidingk-Colorability ofP5-Free Graphs in

✍ Scribed by Chính T. Hoàng; Marcin Kamiński; Vadim Lozin; Joe Sawada; Xiao Shu

Publisher: Springer
Year: 2008
Tongue: English
Weight: 295 KB
Volume: 57
Category: Article
ISSN: 0178-4617
DOI: 10.1007/s00453-008-9197-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Effective on-line coloring ofP5-free gra

Effective on-line coloring ofP5-free graphs

✍ András Gyárfás; Jenő Lehel 📂 Article 📅 1991 🏛 Springer-Verlag 🌐 English ⚖ 235 KB

3-Colorability ∈P for P6-free graphs

✍ Bert Randerath; Ingo Schiermeyer 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 337 KB

In this paper, we study a chromatic aspect for the class of P6-free graphs. Here, the focus of our interest are graph classes (deÿned in terms of forbidden induced subgraphs) for which the question of 3-colorability can be decided in polynomial time and, if so, a proper 3-coloring can be determined

3-Colorability ∈ P for p6–;free Graphs

✍ Bert Randerath; Ingo Schiermeyerb 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 299 KB

On-line graph coloring of({mathbb{P}_5})

On-line graph coloring of({mathbb{P}_5})-free graphs

✍ Iwona Cieślik 📂 Article 📅 2007 🏛 Springer-Verlag 🌐 English ⚖ 381 KB

Coloring algorithms for K5-minor free gr

Coloring algorithms for K5-minor free graphs

✍ Samir Khuller 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 590 KB

List Colorings of K5-Minor-Free Graphs W

List Colorings of K5-Minor-Free Graphs With Special List Assignments

✍ Daniel W. Cranston; Anja Pruchnewski; Zsolt Tuza; Margit Voigt 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L-list colorable for every list assignment L with |L(v)|=min{d(v), 6} for all v ∈ V (G)? More generally, we ask for which pairs (r, k)