4-coloring ($P_6$, bull)-free graphs

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.

References in corpus (5)

• Three-coloring graphs with no induced seven-vertex path II : using a triangle
• Three-coloring graphs with no induced seven-vertex path I : the triangle-free case
• A certifying algorithm for 3-colorability of P5-free graphs
• 4-coloring $P_6$-free graphs with no induced 5-cycles
• Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs