Critical (P₅, bull)-free graphs

DOI10.1016/J.DAM.2023.02.019MaRDI QIDQ6157414zbMATH OpenOpenAlexFDO

Authors Shenwei Huang, Jiawei Li, Wen Xia

Publication date 11 May 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coloringcritical graphsforbidden induced subgraphspolynomial-time algorithmsstrong perfect graph theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given two graphs $H_1$ and $H_2$, a graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ and $C_t$ be the path and the cycle on $t$ vertices, respectively. A bull is the graph obtained from a triangle with two disjoint pendant edges. In this paper, we show that there are finitely many 5-vertex-critical ($P_5$,bull)-free graphs.

Recommendations

• Critical \((P_6, \mathrm{banner})\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• k-critical graphs in P₅-free graphs
• The structure of bull-free perfect graphs
• The structure of bull-free graphs II and III -- a summary

Cites work

• k-critical graphs in P₅-free graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• A note on a conjecture of Dirac
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Certifying coloring algorithms for graphs without long induced paths
• Complexity of coloring graphs without paths and cycles
• Constructions of k-critical P₅-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Dense critical and vertex-critical graphs
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Graph theory
• Note on the colouring of graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• On 3-colorable P₅-free graphs
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Some Theorems on Abstract Graphs
• The strong perfect graph theorem
• Vertex-critical \((P_5\), banner)-free graphs

Cited in

(15)

• Critical \((P_6, \mathrm{banner})\)-free graphs
• A characterization of \(P_5\)-free, diameter-2-critical graphs
• Vertex-critical \((P_5, \mathrm{chair})\)-free graphs
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Vertex-critical ( P₃ + P₁ )-free and vertex-critical (gem, co-gem)-free graphs
• Critical \((P_5,\mathit{dart})\)-free graphs
• Vertex-critical (P₅,W₄)-free graphs
• Some results on critical (P₅, H)-free graphs
• Some results on critical (P₅,H)-free graphs
• Vertex-critical graphs in co-gem-free graphs
• On the finiteness of k-vertex-critical 2P₂-free graphs with forbidden induced squids or bulls
• Critical \(( P_5 , \mathrm{dart} )\)-free graphs
• Vertex-critical (P₅, W₄)-free graphs
• Vertex-critical graphs in subfamilies of (P₄+ P₁)-free graphs
• The structure of bull-free graphs II and III -- a summary

This page was built for publication: Critical (\(P_5\), bull)-free graphs

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