Perfect coloring and linearly χ-bound P6-free graphs
✍ Scribed by S. A. Choudum; T. Karthick; M. A. Shalu
- Publisher
- John Wiley and Sons
- Year
- 2007
- Tongue
- English
- Weight
- 169 KB
- Volume
- 54
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 (cycle) on n vertices and K~1~ + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P~5~, C~4~‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 1995, Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007