4-coloring \((P_6, \text{bull})\)-free graphs

DOI10.1016/j.dam.2016.03.011zbMath1369.05082arXiv1511.08911OpenAlexW2963082826MaRDI QIDQ2403807

Lucas Pastor, Frédéric Maffray

Publication date: 12 September 2017

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

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

zbMATH Keywords

algorithmcoloringpolynomial timebull-free\(P_6\)-free

Mathematics Subject Classification ID

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

Related Items (2)

The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs

Uses Software

• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• 4-colorability of \(P_6\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• On the structure of bull-free perfect graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• A new characterization of \(P_{6}\)-free graphs
• Complement reducible graphs
• Some simplified NP-complete graph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three complexity results on coloring \(P_k\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Handle-rewriting hypergraph grammars
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• 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
• Optimizing Bull-Free Perfect Graphs
• Coloring Bull-Free Perfect Graphs
• On $3$-Colorable $P_5$-Free Graphs
• Reducibility among Combinatorial Problems
• Transitiv orientierbare Graphen

This page was built for publication: 4-coloring \((P_6, \text{bull})\)-free graphs