$(2P_2,K_4)$-Free Graphs are 4-Colorable
$(2P_2,K_4)$-Free Graphs are 4-Colorable
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 …