Even-hole-free graphs still have bisimplicial vertices

DOI10.1016/J.JCTB.2023.02.009zbMATH Open1512.05298arXiv1909.10967OpenAlexW2975372345MaRDI QIDQ6038593FDOQ6038593

Authors: Maria Chudnovsky, Paul Seymour 

Publication date: 2 May 2023

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Even-hole-free graphs: A survey
• Even-hole-free graphs. I: Decomposition theorem
• Bisimplicial vertices in even-hole-free graphs

Cited In (11)

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