Mixing 3-colourings in bipartite graphs
From MaRDI portal
Publication:1039431
DOI10.1016/j.ejc.2009.03.011zbMath1198.05040OpenAlexW2103875227MaRDI QIDQ1039431
Matthew Johnson, Jan van den Heuvel, Luis Cereceda
Publication date: 30 November 2009
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/7398/1/7398.pdf
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (41)
Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ Classifying coloring graphs ⋮ A polynomial version of Cereceda's conjecture ⋮ Finding shortest paths between graph colourings ⋮ In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent ⋮ List-recoloring of sparse graphs ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguration graphs of shortest paths ⋮ Finding Shortest Paths Between Graph Colourings ⋮ The complexity of rerouting shortest paths ⋮ Recoloring graphs via tree decompositions ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Fast recoloring of sparse graphs ⋮ Mixing is hard for triangle-free reflexive graphs ⋮ Digraph redicolouring ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles ⋮ Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ Complexity of independent set reconfigurability problems ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Unnamed Item ⋮ Finding paths between 3-colorings ⋮ Cut-colorings in coloring graphs ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Recoloring graphs of treewidth 2 ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Shortest paths between shortest paths ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Homomorphism complexes and \(k\)-cores ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Distributed Recoloring ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs ⋮ Introduction to reconfiguration
Cites Work
- Computational complexity of compaction to irreflexive cycles
- Connectedness of the graph of vertex-colourings
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Random sampling of 3‐colorings in ℤ2
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Mixing 3-colourings in bipartite graphs
