Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
From MaRDI portal
Publication:5099103
DOI10.1137/21M1443352zbMath1496.05051arXiv2105.01787OpenAlexW3198462604MaRDI QIDQ5099103
Sepehr Hajebi, Sophie Spirkl, Yanjia Li
Publication date: 31 August 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.01787
Related Items (2)
Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
Cites Work
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Linear and 2-frugal choosability of graphs of small maximum average degree
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of colouring problems on dense graphs
- Colouring a graph frugally
- Bounding the vertex cover number of a hypergraph
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- List coloring in the absence of a linear forest
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The NP-Completeness of Edge-Coloring
- Reducibility among Combinatorial Problems
- Four-coloring P6-free graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
