On the tractability of \(( k , i )\)-coloring

DOI10.1016/j.dam.2020.08.018zbMath1476.05048OpenAlexW2951134206MaRDI QIDQ2235289

Saurabh Joshi, Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare

Publication date: 21 October 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://raiith.iith.ac.in/3821/1/1802.03634.pdf

zbMATH Keywords

graph coloringNP-completenessparameterized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Generalized k-tuple colorings of cycles and other graphs
• n-tuple colorings and associated graphs
• Set colourings of graphs
• \(n\)-tuple coloring of planar graphs with large odd girth
• NP-completeness of a family of graph-colouring problems
• Faster deterministic \textsc{Feedback Vertex Set}
• On the tractability of \((k,i)\)-coloring
• Exact and Parameterized Algorithms for (k, i)-Coloring
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Inapproximability of Treewidth and Related Problems
• A note onn-tuple colourings and circular colourings of planar graphs with large odd girth
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On cliques in graphs

This page was built for publication: On the tractability of \(( k , i )\)-coloring