Fixing improper colorings of graphs

DOI10.1016/j.tcs.2017.11.013zbMath1386.68069arXiv1607.06911OpenAlexW2768719733WikidataQ62595886 ScholiaQ62595886MaRDI QIDQ1698729

Konstanty Junosza-Szaniawski, Pedro Montealegre, Paweł Rzążewski, Valentin Garnero, Mathieu Liedloff

Publication date: 16 February 2018

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.06911

zbMATH Keywords

parameterized complexityfixing numberreconfiguration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

On the complexity of restoring corrupted colorings ⋮ Fixing improper colorings of graphs ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of reconfiguration problems
• Reoptimization of the shortest common superstring problem
• Reoptimization of minimum and maximum traveling salesman's tours
• Which problems have strongly exponential complexity?
• Fixing improper colorings of graphs
• Connectedness of the graph of vertex-colourings
• New Reoptimization Techniques applied to Steiner Tree Problem
• A Theory and Algorithms for Combinatorial Reoptimization
• Finding paths between 3-colorings
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Mixing 3-Colourings in Bipartite Graphs
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Set Partitioning via Inclusion-Exclusion
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Fixing improper colorings of graphs