Graphs with No Induced Five‐Vertex Path or Antipath

DOI10.1002/jgt.22022zbMath1359.05083arXiv1410.0871OpenAlexW3125892515MaRDI QIDQ2978172

Frédéric Maffray, Irena Penev, Maria Chudnovsky, Peter Maceli, Laetitia Lemoine, Louis Esperet

Publication date: 21 April 2017

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

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

zbMATH Keywords

decompositionforbidden subgraph\(P_5\)

Mathematics Subject Classification ID

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

Related Items

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Graphs without five-vertex path and four-vertex cycle, The Erdős-Hajnal conjecture for paths and antipaths

Cites Work

• The strong perfect graph theorem
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• A Linear Recognition Algorithm for Cographs
• Four classes of perfectly orderable graphs
• Split Graphs Having Dilworth Number Two
• Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and theH₆-Conjecture