Critical (\(P_5\), bull)-free graphs

DOI10.1016/j.dam.2023.02.019zbMath1512.05140arXiv2211.04179OpenAlexW4324130649MaRDI QIDQ6157414

Jiawei Li, Wen Xia, Shenwei Huang

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

critical graphsforbidden induced subgraphscoloringpolynomial-time algorithmsstrong perfect graph theorem

Mathematics Subject Classification ID

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

Related Items (3)

Vertex-critical \((P_5, \mathrm{chair})\)-free graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

Cites Work

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

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