Perfect coloring and linearly χ‐bound P6‐free graphs
S.A. Choudum, T. Karthick, M. A. Shalu · Journal of Graph Theory · 2006
Abstract We derive decomposition theorems for P6, K1 + P4‐free graphs, P5, K1 + P4‐free graphs and P5, K1 + C4‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, Pn (Cn) denotes the path (cycle) on n vertices and K1 + 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. J Graph Theory 54: 293–306, 2007