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

2015/11/28 by Maffray, Frédéric, Pastor, Lucas
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1511.08911

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₆, bull, gem)-free graphs.

Related

• 4-coloring P₆-free graphs with no induced 5-cycles
• Four-coloring P₆-free graphs. I. Extending an excellent precoloring
• (2P₂,K₄)-Free Graphs are 4-Colorable
• Four-coloring P₆-free graphs. II. Finding an excellent precoloring
• Coloring (P₆, diamond, K₄)-free graphs