List 3-coloring graphs with no induced \(P_6 + rP_3\) (Q2223697)

For graphs \(G\) and \(H\) we denote by \(G+H\) their disjoint union and \(kH\) represents \(k\) copies of \(H\). We also say that \(G\) is \(H\)-free if no induced subgraph of \(G\) is isomorphic to \(H\). A function \(f:V(G)\rightarrow\{1,2,3\}\) is a \(3\)-coloring if \(f(u)\neq f(v)\) for every \(uv\in E(G)\). The \(3\)-coloring problem is the problem of deciding if \(g\) has a \(3\)-coloring for a given graph \(G\). A map \(L\) that assigns a subset of \(\{1,2,3\}\) to every vertex of \(G\) is called a \(3\)-list assignment for \(G\). For a \(3\)-list assignment \(L\) of \(G\) is \(f:V(G)\rightarrow\{1,2,3\}\) a coloring of \((G.L)\) if \(f\) is a coloring of \(G\) and \(f(v)\in L(v)\) for every \(v\in V(G)\). Pair \((G,L)\) is colorable if \((G,L)\) has a coloring. The list \(3\)-coloring problem is the problem of deciding if \((G,L)\) is colorable. The main result of this work is that the list \(3\)-coloring problem can be solved in polynomial time for a class of \((P_6+rP_3)\)-free graphs for every \(r\geq 0\). In contrast to this result, the authors show also that the \(3\)-coloring problem restricted to \((P_5+P_2)\)-free graphs is NP-hard.