Premium
A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
Author(s) -
Feghali Carl,
Johnson Matthew,
Paulusma Daniël
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22000
Subject(s) - combinatorics , mathematics , complete coloring , vertex (graph theory) , fractional coloring , bounded function , list coloring , graph , graph power , greedy coloring , discrete mathematics , brooks' theorem , line graph , mathematical analysis
Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ‐coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k ‐coloring, k > Δ , a Δ‐coloring of G can be obtained by a sequence of O ( n 2 ) recolorings using only the original k colors unless – G is a complete graph or a cycle with an odd number of vertices, or –k = Δ + 1 , G is Δ‐regular and, for each vertex v in G , no two neighbors of v are colored alike. We use this result to study the reconfiguration graphR k ( G )of the k ‐colorings of G . The vertex set ofR k ( G )is the set of all possible k ‐colorings of G and two colorings are adjacent if they differ on exactly one vertex. We prove that for Δ ≥ 3 ,R Δ + 1( G )consists of isolated vertices and at most one further component that has diameter O ( n 2 ) . This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.