Even pairs in square-free Berge graphs with no odd prism
Maffray, Frédéric
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.