4-coloring \((P_6, \text{bull})\)-free graphs
From MaRDI portal
Publication:2403807
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
Related Items (2)
The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs
Uses Software
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 6 ‐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