10 10 -list Recoloring of Planar Graphs

Daniel W. Cranston · 2024

Read 10 10 -list Recoloring of Planar Graphs by Daniel W. Cranston (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00679.txt.

Description

Abstract Fix a planar graph G G and a list assignment L L with | L ⁡ ( v ) | = 10 |L(v)|=10 for all v ∈ V ⁡ ( G ) v\in V(G) . Let α \alpha and β \beta be L L -colorings of G G .

Catalog record

CREATORDaniel W. Cranston
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00679

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

10 10 -list Recoloring of Planar Graphs Daniel W. Cranston Abstract Fix a planar graph G G and a list assignment L L with | L ⁡ ( v ) | = 10 |L(v)|=10 for all v ∈ V ⁡ ( G ) v\in V(G) . Let α \alpha and β \beta be L L -colorings of G G . A recoloring sequence from α \alpha to β \beta is a sequence of L L -colorings, beginning with α \alpha and ending with β \beta , such that each successive pair in the sequence differs in the color on a single vertex of G G . We show that there exists a constant C C such that for all choices of α \alpha and β \beta there exists a recoloring sequence σ \sigma from α \alpha to β \beta that recolors each vertex at most C C times. In particular, σ \sigma has length at most C ​ | V ⁡ ( G ) | C|V(G)| . This confirms a conjecture of Dvořák and Feghali. For our proof, we introduce a new technique for quickly showing that many configurations are reducible. We believe this method may be of independent interest and will have application to other problems in this area. 1 Introduction A recoloring sequence transforms one specified k -coloring of a graph G into another by recoloring one vertex at a time. We also require that each recoloring step yields an intermediate proper k -coloring of G . We typically ask whether every k -coloring can be transformed (or “reconfigured”) to every other. If so, we seek to bound as a function of |G| the maximum number of recoloring steps needed, over all pairs of k -colorings. Analogues of this paradigm have been applied to a broad range of structures including independent sets, dominating sets, solutions to 3-SAT, triangulations of a planar point set, and non-crossing spanning trees, to name a few. This general topic of study is called reconfiguration , and we recommend to the interested reader the surveys [ 11 ] and [ 12 ] and the introduction of [ 2 ] . Perhaps the most widely studied area within reconfiguration is graph coloring, and that is our focus here. Cereceda suggested [ 5 , Conjecture 5.21] that if a graph G is d -degenerate and k\geqslant d+2 , then each k -coloring \alpha of G can be reconfigured to each other k -coloring \beta of G with a recoloring sequence of length O(|G|^{2}) . This problem has attracted much interest and work, including some impressive partial results [ 3 , 10 ] . Nonetheless, the problem remains wide open, even in the case d=2 . In this paper, we consider a list-coloring variant of this conjecture, and we make the lists large enough to guarantee a recoloring sequence with length O(|G|) . Specifically, we focus on graph classes \mathcal{G} and sizes k such that there exists a constant C_{k,\mathcal{G}} satisfying the following: For every graph G\in\mathcal{G} and every k -assignment L and every two L -colorings \alpha and \beta , there exists a recoloring sequence from \alpha to \beta that recolors each vertex at most C_{k,\mathcal{G}} times. Typically, we take \mathcal{G} to be a hereditary class. To prove such a length bound of O(|G|) by induction, we find a “good subgraph” H in G , claim the result for the smaller graph G-H , by the induction hypothesis, and then show that we can extend the result to G precisely because we chose H to be “good”. For these types of arguments, the following Extension Lemma is invaluable. Lemma 1 (Extension Lemma) . Let G be a graph, L be a list assignment for G , and \alpha and \beta be L -colorings for G . Fix v\in V(G) . Let G^{\prime}:=G-v , and let \alpha^{\prime} and \beta^{\prime} be the restrictions to G^{\prime} of \alpha and \beta . Suppose there exists a recoloring sequence \sigma^{\prime} that recolors G from \alpha^{\prime} to \beta^{\prime} . If \sigma^{\prime} recolors vertices in N(v) a total of s times, then \sigma^{\prime} extends to a recoloring sequence \sigma for G from \alpha to \beta that recolors v at most \left\lceil\frac{s}{|L(v)|-d(v)-1}\right\rceil+1 times. Proof. Let c_{1},\ldots,c_{s} denote the colors that are used by \sigma^{\prime} to recolor N(v) , with multiplicity and in order. We show how to extend \sigma^{\prime} to \sigma . Each time that \sigma will recolor N(v) with some c_{i} that is currently used on v , we must first recolor v before we can continue with the recoloring step in \sigma^{\prime} . Let a:=|L(v)|-d(v)-1 . We must avoid all colors currently used on N(v) , as well as c_{i} , so we have at least a choices. We choose a color that does not appear among c_{i},c_{i+1},\ldots,c_{i+a-1} . Thus, the number of times that we must recolor v , due to its current color being needed on N(v) , is at most \left\lceil\frac{s}{|L(v)|-d(v)-1}\right\rceil . To conclude, we may need one more step to recolor v to match \beta(v) . ∎ The Extension Lemma has been used implicitly in many papers; it was first stated explicitly for coloring in [ 1 ] , and generalized to list-coloring (with the same proof) in [ 7 ] . We note also that the same proof works in the more general context of “correspondence” coloring; however, we omit the definitions needed to make this formal, since including them would only add more abstraction without adding any more interesting ideas. (In fact, nearly all of the arguments in this paper work equally well for correspondence coloring. However, we will not mention this in what follows.) For a graph G and list assignment L , let \mathcal{C}_{L}(G) † † margin: \mathcal{C}_{L}(G) denote the graph with a node for each L -coloring of G and an edge between each pair of nodes that differ only in the color of a single vertex of G . Bousquet and Perarnau [ 4 ] used the Extension Lemma to prove the following pretty result. Lemma 2 ( [ 4 ] ) . If G is a d -degenerate graph and L is a list assignment with |L(v)|\geqslant 2d+2 for all v\in V(G) , then \textrm{diam}~\mathcal{C}_{L}(G)\leqslant(d+1)|G| . Proof. Let L be a list assignment as in the lemma, and fix L -colorings \alpha and \beta . We prove that G can be recolored from \alpha to \beta such that each vertex is recolored at most d+1 times. Pick v such that d(v)\leqslant d . Let G^{\prime}:=G-v , and let \alpha^{\prime} and \beta^{\prime} denote the restrictions to G^{\prime} of \alpha and \beta . By hypothesis, there exists a sequence \sigma^{\prime} that recolors G from \alpha^{\prime} to \beta^{\prime} and recolors each vertex at most d+1 times. By the Extension Lemma, we can extend \sigma^{\prime} to a sequence \sigma that recolors v at most \left\lceil\frac{|N(v)|(d+1)}{2d+2-(d+1)}\right\rceil+1=|N(v)|+1\leqslant d+1 times. ∎ Conjecture 3 . Let k,d be positive integers with k\geqslant d+3 . There exists a constant 1 1 1 A priori, we might want to allow C_{d} to also depend on k , but the stated version is equivalent, as follows. If the weaker version is true, then C^{k}_{d} exists for each k\geqslant d+3 . Let C_{d}:=\max\{d+1,\max_{d+3\leqslant

Read the complete text