Name
Title | ||
|---|---|---|
Finding Paths between Graph Colourings: Computational Complexity and Possible Distances |
Abstract | ||
|---|---|---|
Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouring of G? |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.endm.2007.07.073 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
colour graph,PSPACE-completeness,superpolynomial paths | Graph canonization,Discrete mathematics,Graph toughness,Combinatorics,Graph power,Cycle graph,Vertex cover,Graph minor,Mathematics,Feedback vertex set,Complement graph | Journal |
Volume | ISSN | Citations |
29 | 1571-0653 | 5 |
PageRank | References | Authors |
0.64 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Bonsma | 1 | 287 | 20.46 |
| Luis Cereceda | 2 | 156 | 10.77 |
| Jan van den Heuvel | 3 | 361 | 34.75 |
| Matthew Johnson | 4 | 197 | 23.20 |