First-Fit coloring of {P5,K4?e} { P 5 , K 4 ? e } -free graphs
We show that given any ordering of the vertices of a {P5,K4?e} { P 5 , K 4 ? e } -free graph G G , the First-Fit coloring algorithm colors its vertices using at most 2?(G)?1 2 ? ( G ) ? 1 colors (where ?(G) ? ( G ) is the clique number of G G ) via a characterization proved by using the known results. We also construct {P5,K4?e} { P 5 , K 4 ? e } -free graphs to show that this bound cannot be improved. A similar result is proved for the class of {P5,paw} { P 5 , p a w } -free graphs.
first-fit coloring clique number p5 p 5 -free graphs p5 p 5 p5 p 5 p 5 paw-free graphs on-line coloring