On the tractability of ( k , i )-coloring

DOI10.1016/J.DAM.2020.08.018zbMATH Open1476.05048OpenAlexW2951134206MaRDI QIDQ2235289FDOQ2235289

Authors: Sriram Bhyravarapu, Saurabh Joshi, 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

Recommendations

• On the tractability of \((k,i)\)-coloring
• Exact and parameterized algorithms for \((k,i)\)-coloring
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Fixed-parameter tractability of \((n-k)\) list coloring
• Fixed-parameter tractability of \((n-k)\) list coloring
• On the \(k\)-coloring of intervals
• scientific article; zbMATH DE number 1564005
• scientific article; zbMATH DE number 1433954
• On the complexity of \(k\)-rainbow cycle colouring problems
• On restricted colourings of \(K_ n\)

zbMATH Keywords

graph coloringNP-completenessparameterized algorithms

Mathematics Subject Classification ID

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

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Exact exponential algorithms.
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• On cliques in graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Isomorphism for graphs of bounded feedback vertex set number
• n-tuple colorings and associated graphs
• Set colourings of graphs
• Faster deterministic \textsc{Feedback Vertex Set}
• Title not available (Why is that?)
• Generalized k-tuple colorings of cycles and other graphs
• \(n\)-tuple coloring of planar graphs with large odd girth
• Inapproximability of treewidth and related problems
• NP-completeness of a family of graph-colouring problems
• On the tractability of \((k,i)\)-coloring
• Exact and parameterized algorithms for \((k,i)\)-coloring
• On the \((k,i)\)-coloring of cacti and complete graphs.
• A note onn-tuple colourings and circular colourings of planar graphs with large odd girth

Cited In (3)

• Exact and parameterized algorithms for \((k,i)\)-coloring
• On the \((k,i)\)-coloring of cacti and complete graphs.
• On the tractability of \((k,i)\)-coloring

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

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