First-Fit coloring of {P5,K4−e}{P5,K4−e}-free graphs

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