Distributed Recoloring
From MaRDI portal
Publication:5090902
DOI10.4230/LIPIcs.DISC.2018.12zbMath1497.68369arXiv1802.06742OpenAlexW2795608362MaRDI QIDQ5090902
Marthe Bonamy, Jukka Suomela, Paul Ouvrard, Jara Uitto, Mikaël Rabie
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1802.06742
Network design and communication in computer systems (68M10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (4)
Distributed reconfiguration of maximal independent sets ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Brief announcement: Distributed reconfiguration of spanning trees ⋮ Distributed Reconfiguration of Maximal Independent Sets
Cites Work
- Fast recoloring of sparse graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Kempe classes and the Hadwiger conjecture
- Recoloring graphs via tree decompositions
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
- A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Finding paths between 3-colorings
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed Coloring in Sparse Graphs with Fewer Colors
- An optimal distributed (Δ+1)-coloring algorithm?
- Brief Announcement
- LCL Problems on Grids
- Kempe equivalence of colourings of cubic graphs
This page was built for publication: Distributed Recoloring
