Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Berge graphs
- Even pairs
- Perfect graphs