Parameterized complexity of list coloring and max coloring

DOI10.1007/978-3-031-09574-0_4OpenAlexW4285307874MaRDI QIDQ2097212

Bardiya Aryanfard, Fahad Panolan

Publication date: 11 November 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-09574-0_4

zbMATH Keywords

reductiongraph coloringfixed parameter tractabilityrandomized algorithmsexponential time hypothesis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• A probabilistic remark on algebraic program testing
• Saving colors and max coloring: some fixed-parameter tractability results
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Weighted Coloring in Trees
• Parameterized Pre-Coloring Extension and List Coloring Problems
• Ruling out FPT algorithms for weighted coloring on forests
• On the complexity of \(k\)-SAT