Even pairs in square-free Berge graphs with no odd prism
classification
🧮 math.CO
keywords
classbergeeveneverygraphgraphsprismalgorithm
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.