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

maximum average degreetriangle-free planar graphlist-assignment\(L\)-recoloring sequence

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.

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 Thomassen-type method for planar graph recoloring
• A polynomial version of Cereceda's conjecture
• A survey on the use of Markov chains to randomly sample colourings
• 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

(7)

• Reconfiguration of list edge-colorings in a graph
• List Dynamic Coloring of Sparse Graphs
• Linear list r-hued coloring of sparse graphs
• Reconfiguration of List Edge-Colorings in a Graph
• Fast recoloring of sparse graphs
• List recoloring of planar graphs
• List-Coloring Squares of Sparse Subcubic 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)