Cut-Colorings in Coloring Graphs
DOI
https://doi.org/10.1007/s00373-018-1985-6
Abstract
This paper studies the connectivity and biconnectivity of coloring graphs. For kN, the k-coloring graph of a base graph G has vertex set consisting of the proper k-colorings of G and edge set consisting of the pairs of k-colorings that differ on a single vertex. A base graph whose k-coloring graph is connected is said to be k-mixing; it is possible to transition between any two k-colorings in a k-mixing graph via a sequence of single vertex recolorings, where each intermediate step is also a proper k-coloring. A natural extension of connectedness is biconnectedness. If a base graph has a coloring graph that is not biconnected, then there exists a proper k-coloring that would disconnect the coloring graph if removed. We call such a coloring a k-cut coloring. We prove that no base graph that is 3-mixing can have a 3-cut coloring, but for any k4 there exists a base graph that is k-mixing and has a k-cut coloring.
Document Type
Article
Publication Date
1-2019
Publisher Statement
Copyright © 2019, SpringerLink DOI: https://doi.org/10.1007/s00373-018-1985-6 The definitive version is available at: Graphs and Combinatorics 2 / 2
Recommended Citation
Bhakta, Prateek, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, and Heather M. Russell. “Cut-Colorings in Coloring Graphs.” Graphs and Combinatorics 35, no. 1 (January 2019): 239–48. https://doi.org/10.1007/s00373-018-1985-6.