$(2P_2,K_4)$-Free Graphs are 4-Colorable
Serge Gaspers, Shenwei Huang · SIAM Journal on Discrete Mathematics · 2019
In this paper, we show that every $(2P_2,K_4)$-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [ J. Combin. Theory Ser. B, 29 (1980), pp. 345--346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for $(4P_1,C_4)$-free graphs. Lozin and Malyshev [ Discrete Appl. Math., 216 (2017), pp. 273--280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring $(4P_1,C_4)$-free graphs.