Affordable Access

Publisher Website

How To Color Claw-Free Perfect Graphs**This work was supported by National Science Foundation grant ENG 75-00568 to Cornell University.

DOI: 10.1016/s0304-0208(08)73466-2
  • Computer Science


An O(n4) minimum coloring algorithm on claw-free perfect graphs is presented. The algorithm proceeds recursively as follows. Let x be any vertex of G. Having colored the subgraph G\x using no more than ω(G) (the size of a maximum clique in G) colors, the algorithm shows how to color G using no more than ω(G) colors. The algorithm demonstrates that the size of a minimum coloring is equal to the size of a maximum clique for graphs containing no claws, odd holes or odd anti-holes, hence it provides an alternative proof that the strong perfect graph conjecture is true for claw-free graphs.

There are no comments yet on this publication. Be the first to share your thoughts.