Even pairs in square-free Berge graphs with no odd prism
arXiv:1502.03695
Abstract
We consider the class of Berge graphs that contain no odd prism and no square (cycle on four vertices). We prove that every graph G in this class either is a clique or has an even pair, as conjectured by Everett and Reed. This result is used to devise a polynomial-time algorithm to color optimally every graph in this class.
arXiv admin note: text overlap with arXiv:math/0212070, arXiv:1301.5149 by other authors