Luis Cereceda
Mixing 3-colourings in bipartite graphs
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
Abstract
For a 3-colourable graph G, the 3-colour graph of G, denoted C_3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question: given G, how easily can one decide whether or not C_3(G) is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which View the MathML source is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.
Citation
Cereceda, L., van den Heuvel, J., & Johnson, M. (2009). Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7), 1593-1606. https://doi.org/10.1016/j.ejc.2009.03.011
Journal Article Type | Article |
---|---|
Publication Date | Oct 1, 2009 |
Deposit Date | Sep 30, 2010 |
Publicly Available Date | Oct 29, 2010 |
Journal | European Journal of Combinatorics |
Print ISSN | 0195-6698 |
Electronic ISSN | 1095-9971 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 30 |
Issue | 7 |
Pages | 1593-1606 |
DOI | https://doi.org/10.1016/j.ejc.2009.03.011 |
Public URL | https://durham-repository.worktribe.com/output/1516038 |
Files
Accepted Journal Article
(393 Kb)
PDF
Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in European journal of combinatorics.
You might also like
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Computing weighted subset odd cycle transversals in H-free graphs
(2022)
Journal Article
Computing subset transversals in H-free graphs
(2021)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search