We consider the class of Berge graphs that do not contain an induced cycle of length four. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Berge graph