List-coloring -- parameterizing from triviality
From MaRDI portal
Publication:2173305
DOI10.1016/j.tcs.2020.02.022zbMath1437.68069OpenAlexW3009168115MaRDI QIDQ2173305
Venkatesh Raman, Vijay Kumar Paliwal, Aritra Banik, Pranav Arora
Publication date: 22 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.02.022
Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Finding odd cycle transversals.
- Almost 2-SAT is fixed-parameter tractable
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Some simplified NP-complete graph problems
- Every planar graph is 5-choosable
- Parameterized complexity of vertex colouring
- Parameterized complexity of finding subgraphs with hereditary properties.
- Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21--23, 2004. Revised papers.
- Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
- Open Problems on Graph Coloring for Special Graph Classes
- Set Partitioning via Inclusion-Exclusion
- Simpler Parameterized Algorithm for OCT
- Faster Parameterized Algorithms Using Linear Programming
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Graph-Theoretic Concepts in Computer Science
- Fixed-parameter tractability of \((n-k)\) list coloring
This page was built for publication: List-coloring -- parameterizing from triviality
