A polynomial version of Cereceda's conjecture
From MaRDI portal
Publication:2131856
DOI10.1016/j.jctb.2022.01.006zbMath1493.05096arXiv1903.05619OpenAlexW4210673793MaRDI QIDQ2131856
Marc Heinrich, Nicolas Bousquet
Publication date: 27 April 2022
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.05619
Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (6)
Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ List-recoloring of sparse graphs ⋮ Optimally reconfiguring list and correspondence colourings ⋮ Digraph redicolouring ⋮ Strengthening a Theorem of Meyniel ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Fast recoloring of sparse graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Paths between colourings of sparse graphs
- Recoloring graphs via tree decompositions
- Flipping edge-labelled triangulations
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
- Introduction to reconfiguration
- Reconfiguring 10-colourings of planar graphs
- A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
- The complexity of change
- Finding paths between 3-colorings
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Frozen (Δ + 1)-colourings of bounded degree graphs
- Toward Cereceda's conjecture for planar graphs
- Improved Bounds for Randomly Sampling Colorings via Linear Programming
This page was built for publication: A polynomial version of Cereceda's conjecture
