### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1119-1164 |

Number of pages | 46 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 98 |

Issue number | 6 |

DOIs | |

State | Published - Nov 2008 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Bisimplicial vertices
- Colouring
- Even holes
- Induced subgraphs

## Fingerprint Dive into the research topics of 'Bisimplicial vertices in even-hole-free graphs'. Together they form a unique fingerprint.

## Cite this

Addario-Berry, L., Chudnovsky, M., Havet, F., Reed, B., & Seymour, P. (2008). Bisimplicial vertices in even-hole-free graphs.

*Journal of Combinatorial Theory. Series B*,*98*(6), 1119-1164. https://doi.org/10.1016/j.jctb.2007.12.006