First-Fit coloring of {P<inf>5</inf>, K<inf>4</inf> - e}-free graphs

We show that given any ordering of the vertices of a {P5, K4 - e}-free graph G, the First-Fit coloring algorithm colors its vertices using at most 2 ω (G) - 1 colors (where ω (G) is the clique number of G) via a characterization proved by using the known results. We also construct {P5, K4 - e}-free graphs to show that this bound cannot be improved. A similar result is proved for the class of {P5, p a w}-free graphs. © 2009 Elsevier B.V. All rights reserved.