4-coloring (P₆, bull)-free graphs

DOI10.1016/J.DAM.2016.03.011MaRDI QIDQ2403807zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Lucas Pastor

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

\(P_6\)-freealgorithmbull-freecoloringpolynomial time

Mathematics Subject Classification ID

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

Abstract: We present a polynomial-time algorithm that determines whether a graph that contains no induced path on six vertices and no bull (the graph with vertices a, b, c, d, e and edges ab, bc, cd, be, ce) is 4-colorable. We also show that for any fixed k the k-coloring problem can be solved in polynomial time in the class of ($P_6$, bull, gem)-free graphs.

Recommendations

• Four-coloring \(P_6\)-free graphs
• 4-colorability of P₆-free graphs
• Complexity of coloring graphs without paths and cycles
• 4-coloring \(H\)-free graphs when \(H\) is small
• 4-coloring \(H\)-free graphs when \(H\) is small

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 4-colorability of P₆-free graphs
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new characterization of \(P_{6}\)-free graphs
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Coloring bull-free perfect graphs
• Complement reducible graphs
• Constructions of k-critical P₅-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• On 3-colorable P₅-free graphs
• On the structure of bull-free perfect graphs
• Optimizing Bull-Free Perfect Graphs
• Reducibility among combinatorial problems
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Some simplified NP-complete graph problems
• The strong perfect graph theorem
• Three complexity results on coloring \(P_k\)-free graphs
• Transitiv orientierbare Graphen
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Upper bounds to the clique width of graphs

Cited in

(10)

• Critical \((P_6, \mathrm{banner})\)-free graphs
• Solving the clique cover problem on (bull, \(C_4\))-free graphs
• The maximum weight stable set problem in (P₆, bull)-free graphs
• 4-colorability of P₆-free graphs
• Optimizing Bull-Free Perfect Graphs
• Coloring bull-free perfect graphs
• Four-coloring \(P_6\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• There are finitely many 5-vertex-critical \((P_6, \mathrm{bull})\)-free graphs

Describes a project that uses

Uses Software

• CriticalPfreeGraphs

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

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