Bounded obstructions for three-coloring graphs with lists size two

Abstract

Excluding certain subgraphs H from non-3-colorable graphs results in classes of graphs that do or do not have bounded obstructions to coloring. In the positive case, we call those subgraphs H powerful. When the graphs are given a list function L with lists of size 2, we call such H 2-powerful. In this paper we classify all graphs as either 2-powerful or not. In particular, we use propagation paths to show in a simpler way that P\(_{5}\) and P\(_{2}\) + P\(_{3}\) are 2-powerful.