Perfect coloring and linearly χ-bound P<inf>6</inf>-free graphs

We derive decomposition theorems for {P6, K1 + P 4}-free graphs, {P5, K1 + P4}-free graphs and {P5, K1 + C4}-free graphs, and deduce linear χ-binding functions for these classes of graphs (here, P n(Cn) 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 {P5, C4}-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.