List 3-coloring graphs with no induced P₆ + rP₃
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.
- Colouring \((P_r + P_s)\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Bounding the vertex cover number of a hypergraph
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Colouring \((P_r + P_s)\)-free graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- The complexity of colouring problems on dense graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Injective colouring for H-free graphs
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Colouring \((P_r + P_s)\)-free graphs
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- List k-colouring P_t-free graphs: a mim-width perspective
- List coloring in the absence of a linear forest
- 3-colorability \(\in\mathrm{P}\) for \(P_{6}\)-free graphs
- List coloring in the absence of a linear forest
- Obstructions for three-coloring graphs with one forbidden induced subgraph
- Colouring (P_r+P_s)-Free Graphs
- Colouring H-free graphs of bounded diameter.
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Vertex-critical ( P₃ + P₁ )-free and vertex-critical (gem, co-gem)-free graphs
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- Acyclic, star and injective colouring: a complexity picture for H-free graphs
- Vertex-critical graphs in co-gem-free graphs
- Minimal obstructions to C₅-Coloring in hereditary graph classes
- Minimal obstructions to C₅-coloring in hereditary graph classes
This page was built for publication: List 3-coloring graphs with no induced \(P_6 + rP_3\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223697)
