×

zbMATH — the first resource for mathematics

Even pairs in square-free Berge graphs. (English) Zbl 1049.05041
Summary: We consider the graphs that contain no odd chordless cycle on at least five vertices (an “odd hole”), no chordless cycle on exactly four vertices (a “square”), and no subgraph that consists of two triangles with three vertex-disjoint paths between them (a “stretcher”). We show that any such graph either is a complete graph or has two vertices that are not linked by an odd chordless path (an “even pair”). This is a partial answer, in the case of square-free graphs, to several conjectures concerning even pairs in Berge graphs.

MSC:
05C17 Perfect graphs
PDF BibTeX XML Cite