Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the H₆-conjecture

DOI10.1002/JGT.21763MaRDI QIDQ5495885zbMATH OpenOpenAlexWikidataFDO

Authors Maria Chudnovsky, Peter Maceli

Publication date 7 August 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

antipathinduced subgraphpath

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let $mathcalG$ be the class of all graphs with no induced four-edge path or four-edge antipath. Hayward and Nastos cite{MS} conjectured that every prime graph in $mathcalG$ not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this paper we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour cite{grow} we give a short proof of Fouquet's result cite{C5} on the structure of the subclass of bull-free graphs contained in $mathcalG$.

Recommendations

• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Excluding paths and antipaths
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• Graphs with No Induced Five‐Vertex Path or Antipath
• Triangle-free graphs with no six-vertex induced path

Cites work

• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Growing without cloning
• On a property of the class of n-colorable graphs
• On brittle graphs
• Some classes of perfectly orderable graphs

Cited in

(3)

• The Erdős-Hajnal conjecture for paths and antipaths
• Graphs with No Induced Five‐Vertex Path or Antipath
• On minimally t-tough graphs with t 1

This page was built for publication: Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the \(H_{6}\)-conjecture

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