The intersection of two vertex coloring problems

2019/04/17 by Foley, Angele M., Fraser, Dallas J., Hoang, Chinh T. +2 · 1 citation
#68R05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1904.08180

Abstract

A hole is an induced cycle with at least four vertices. A hole is even if its number of vertices is even. Given a set L of graphs, a graph G is L-free if G does not contain any graph in L as an induced subgraph. Currently, the following two problems are unresolved: the complexity of coloring even hole-free graphs, and the complexity of coloring 4K1, C4-free graphs. The intersection of these two problems is the problem of coloring 4K1, C4, C6-free graphs. In this paper we present partial results on this problem.

Cited by

• On the structure of (4K₁, C₄, P₆)-free graphs

Related

• A Note on Coloring (4K₁, C₄, C₆)-free graphs with a C₇
• A note on coloring (even-hole,cap)-free graphs
• Coloring of graphs without long odd holes
• Coloring even-hole-free graphs with no star cutset
• On the chromatic number of a family of odd hole free graphs