List-recoloring of sparse graphs

DOI10.1016/J.EJC.2022.103562MaRDI QIDQ2145762zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston

Publication date 20 June 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.05133

zbMATH Keywords

\(L\)-recoloring sequencelist-assignmentmaximum average degreetriangle-free planar graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: Fix a graph $G$, a list-assignment $L$ for $G$, and $L$-colorings $alpha$ and $$. An $L$-recoloring sequence, starting from $alpha$, recolors a single vertex at each step, so that each resulting intermediate coloring is a proper $L$-coloring. An $L$-recoloring sequence transforms $alpha$ to $$ if its initial coloring is $alpha$ and its final coloring is $$. We prove there exists an $L$-recoloring sequence that transforms $alpha$ to $$ and recolors each vertex at most a constant number of times if (i) $G$ is triangle-free and planar and $L$ is a 7-assignment, or (ii) $mathrmmad(G)<17/5$ and $L$ is a 6-assignment or (iii) $mathrmmad(G)<22/9$ and $L$ is a 4-assignment. Parts (i) and (ii) confirm conjectures of Dvov{r}'{a}k and Feghali.

Review text

For a list-assignment \(L\) for a graph \(G\), and \(L\)-colorings \(\alpha\) and \(\beta\), an \(L\)-recoloring sequence, starting from \(\alpha\), recolors a single vertex at each step, so that each resulting intermediate coloring is a proper \(L\)-coloring. In this paper, the author proves that there exists an \(L\)-recoloring sequence that transforms \(\alpha\) to \(\beta\) and recolors each vertex at most a constant number of times if (i) \(G\) is triangle-free and planar and \(L\) is a 7-assignment (at most 30 times), or (ii) mad(\(G\)) < 17/5 and \(L\) is a 6-assignment (at most 12 times) or (iii) mad(G) < 22/9 and \(L\) is a 4-assignment (at most 14 times), where mad denotes maximum average degree. Parts (i) and (ii) confirm conjectures of \textit{Z. Dvořák} and \textit{C. Feghali} [Electron. J. Comb. 27, No. 4, Research Paper P4.51, 21 p. (2020; Zbl 1457.05033)].

Recommendations

• Fast recoloring of sparse graphs
• Reconfiguration of list edge-colorings in a graph
• Reconfiguration of List Edge-Colorings in a Graph
• List Dynamic Coloring of Sparse Graphs
• 2-distance list \((\varDelta +3)\)-coloring of sparse graphs

Cites work

• A polynomial version of Cereceda's conjecture
• A survey on the use of Markov chains to randomly sample colourings
• A Thomassen-type method for planar graph recoloring
• An update on reconfiguring 10-colorings of planar graphs
• Fast recoloring of sparse graphs
• Improved bounds for randomly sampling colorings via linear programming
• Introduction to reconfiguration
• Linear choosability of sparse graphs
• Mixing 3-colourings in bipartite graphs
• Paths between colourings of sparse graphs
• Recoloring graphs via tree decompositions
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• The complexity of change

Cited in

(11)

• Reconfiguration of List Edge-Colorings in a Graph
• List-Coloring Squares of Sparse Subcubic Graphs
• Linear list r-hued coloring of sparse graphs
• List Dynamic Coloring of Sparse Graphs
• List recoloring of planar graphs
• Sharp bounds on lengths of linear recolouring sequences
• 10-list recoloring of planar graphs
• Reconfiguration graphs for vertex colorings of P₅-free graphs
• Reconfiguration of list edge-colorings in a graph
• List recoloring of planar graphs without 4-cycles
• Fast recoloring of sparse graphs

This page was built for publication: List-recoloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145762)