pith. sign in

arxiv: 1502.03695 · v1 · pith:BB7JPTWFnew · submitted 2015-02-12 · 🧮 math.CO

Even pairs in square-free Berge graphs with no odd prism

classification 🧮 math.CO
keywords classbergeeveneverygraphgraphsprismalgorithm
0
0 comments X
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.