List 3-coloring graphs with no induced P₆ + rP₃
From MaRDI portal
Publication:2223697
DOI10.1007/S00453-020-00754-YOpenAlexW3046505698MaRDI QIDQ2223697FDOQ2223697
Maria Chudnovsky, Mingxian Zhong, Shenwei Huang, Sophie Spirkl
Publication date: 1 February 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00754-y
Recommendations
- 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.
Cites Work
- The complexity of colouring problems on dense graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Colouring \((P_r + P_s)\)-free graphs
- Bounding the vertex cover number of a hypergraph
- Closing complexity gaps for coloring problems on \(H\)-free graphs
Cited In (12)
- Injective colouring for H-free graphs
- Colouring H-free graphs of bounded diameter.
- 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
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Colouring \((P_r + P_s)\)-free graphs
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
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)
