Fixing improper colorings of graphs
From MaRDI portal
Publication:1698729
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
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
