List-coloring -- parameterizing from triviality

DOI10.1016/J.TCS.2020.02.022MaRDI QIDQ2173305zbMATH OpenOpenAlexFDO

Authors Pranav Arora, Aritra Banik, Vijay Kumar Paliwal, Venkatesh Raman

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

zbMATH Keywords

FPTgraph coloringlist coloringparameterized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Fixed-parameter tractability of (n-k) list coloring
• Some (in)tractable parameterizations of coloring and list-coloring
• Fixed-parameter tractability of \((n-k)\) list coloring
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover

Cites work

• Almost 2-SAT is fixed-parameter tractable
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Coloring graphs with forbidden induced subgraphs
• Every planar graph is 5-choosable
• Faster parameterized algorithms using linear programming
• Filling the complexity gaps for colouring planar and bounded degree graphs
• Finding odd cycle transversals.
• Fine-grained parameterized complexity analysis of graph coloring problems
• Fixed-parameter tractability of \((n-k)\) list coloring
• Graph-Theoretic Concepts in Computer Science
• Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21--23, 2004. Revised papers.
• Open problems on graph coloring for special graph classes
• Parameterized algorithms
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized complexity of vertex colouring
• Set partitioning via inclusion-exclusion
• Simpler parameterized algorithm for OCT
• Some simplified NP-complete graph problems
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(7)

• Parameterized pre-coloring extension and list coloring problems
• Fixed-parameter tractability of (n-k) list coloring
• Fixed-parameter tractability of \((n-k)\) list coloring
• Consensus models: computational complexity aspects in modern approaches to the list coloring problem
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Dominator coloring and CD coloring in almost cluster graphs
• Some (in)tractable parameterizations of coloring and list-coloring

This page was built for publication: List-coloring -- parameterizing from triviality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173305)