Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657260 | Journal of Combinatorial Theory, Series B | 2008 | 46 Pages |
Abstract
A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. In this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics