Avoidable paths in graphs

DOI10.37236/9030zbMATH Open1454.05058arXiv1908.03788OpenAlexW3113066384MaRDI QIDQ2215468FDOQ2215468

Authors: Marthe Bonamy, Oscar Defrain, Meike Hatzel, Jocelyn Thiebaut 

Publication date: 13 December 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs. The conjecture was only established for k in {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively). Our result also implies a result of Chv'atal et al. 2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis. In the line of previous works, we discuss conditions for multiple avoidable paths to exist.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Avoidable vertices and edges in graphs
• Finding paths in graphs avoiding forbidden transitions
• Some results on path-factor critical avoidable graphs
• Computing and listing avoidable vertices and paths
• Keeping avoider's graph almost acyclic
• Simple Paths and Cycles Avoiding Forbidden Paths
• Pattern avoidance on graphs
• scientific article; zbMATH DE number 4147534
• Paths in graphs
• Avoidable vertices and edges in graphs: existence, characterization, and applications

zbMATH Keywords

avoidableavoidable path

Mathematics Subject Classification ID

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

Cites Work

• Dirac-type characterizations of graphs without long chordless cycles
• On rigid circuit graphs
• Separability generalizes Dirac's theorem
• Vertex elimination orderings for hereditary graph classes

Cited In (7)

• Graphs with at most two moplexes
• Computing and listing avoidable vertices and paths
• Shifting paths to avoidable ones
• Simple Paths and Cycles Avoiding Forbidden Paths
• Absolutely avoidable order-size pairs for induced subgraphs
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Computing and listing avoidable vertices and paths

This page was built for publication: Avoidable paths in graphs

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