✦ LIBER ✦

3-Colorability ∈ P for p6–;free Graphs

✍ Scribed by Bert Randerath; Ingo Schiermeyerb

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 299 KB
Volume: 8
Category: Article
ISSN: 1571-0653
DOI: 10.1016/s1571-0653(05)80088-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Perfect coloring and linearly χ-bound P6

Perfect coloring and linearly χ-bound P6-free graphs

✍ S. A. Choudum; T. Karthick; M. A. Shalu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

## Abstract We derive decomposition theorems for __P__~6~, __K__~1~ + __P__~4~‐free graphs, __P__~5~, __K__~1~ + __P__~4~‐free graphs and __P__~5~, __K__~1~ + __C__~4~‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, __P__~__n__~ (__C__~__n__~) denotes the path

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

On 3-colorings of bipartite p-threshold

On 3-colorings of bipartite p-threshold graphs

✍ Ioan Tomescu 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 510 KB

P3-isomorphisms for graphs

✍ Aldred, R. E. L.; Ellingham, M. N.; Hemminger, R. L.; Jipsen, P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

The P 3 -graph of a finite simple graph G is the graph whose vertices are the 3-vertex paths of G, with adjacency between two such paths whenever their union is a 4-vertex path or a 3-cycle. In this paper we show that connected finite simple graphs G and H with isomorphic P 3 -graphs are either isom

Claw-free 3-connected P11-free graphs ar

Claw-free 3-connected P11-free graphs are hamiltonian

✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T