✦ LIBER ✦

Updating the complexity status of coloring graphs without a fixed induced linear forest

✍ Scribed by Hajo Broersma; Petr A. Golovach; Daniël Paulusma; Jian Song

Book ID: 113927569
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 330 KB
Volume: 414
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.10.005

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the parameterized complexity of color

On the parameterized complexity of coloring graphs in the absence of a linear forest

✍ Couturier, Jean-François; Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 182 KB

On the maximum induced forests of a conn

On the maximum induced forests of a connected cubic graph without triangles

✍ Maolin Zheng; Xiaoyun Lu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 438 KB

Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. For connected simple cubic graphs G without triangles, it is shown that r(G) 3 2n/3 except for two particular graphs. This lower bound is sharp and it improves a result due to J.A. Bondy, et al. [l]. Using this