Even-hole-free graphs still have bisimplicial vertices

DOI10.1016/J.JCTB.2023.02.009MaRDI QIDQ6038593zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Paul Seymour

Publication date 2 May 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.10967

zbMATH Keywords

induced subgrapheven-hole-free graphbisimplicial vertex

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Abstract: A {em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {em even} if it has an even number of vertices. An {em even-hole-free} graph is a graph with no even holes. A vertex of a graph is {em bisimplicial} if the set of its neighbours is the union of two cliques. In an earlier paper cite{bisimplicial}, Addario-Berry, Havet and Reed, with the authors, claimed to prove a conjecture of Reed, that every even-hole-free graph has a bisimplicial vertex, but we have recently been shown that the "proof" has a serious error. Here we give a proof using a different method.

Recommendations

• Bisimplicial vertices in even-hole-free graphs
• Some remarks on even-hole-free graphs
• The intersection of two vertex coloring problems
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences

Cites work

• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• Bisimplicial vertices in even-hole-free graphs
• Even-hole-free graphs. I: Decomposition theorem
• Even-hole-free graphs: A survey

Cited in

(11)

• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• Some remarks on even-hole-free graphs
• Graphs with no even holes and no sector wheels are the union of two chordal graphs
• On the chromatic number of a family of odd hole free graphs
• Corrigendum to: ``Bisimplicial vertices in even-hole-free graphs
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Graphs with girth 9 and without longer odd holes are 3-colourable
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• From \(\chi\)- to \(\chi_p\)-bounded classes
• Hitting all maximum stable sets in \(P_5\)-free graphs
• Bisimplicial vertices in even-hole-free graphs

This page was built for publication: Even-hole-free graphs still have bisimplicial vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038593)