List recoloring of planar graphs

• Published in: arXiv.org 2022-11
• Main Authors: L Sunil Chandran, Gupta, Uttam K, Pradhan, Dinabandhu
• Format: Article
• Language: English
• Subjects: Apexes; Coloring; Graph theory
• ISSN: 2331-8422

A list assignment \(L\) of a graph \(G\) is a function that assigns to every vertex \(v\) of \(G\) a set \(L(v)\) of colors. A proper coloring \(\alpha\) of \(G\) is called an \(L\)-coloring of \(G\) if \(\alpha(v)\in L(v)\) for every \(v\in V(G)\). For a list assignment \(L\) of \(G\), the \(L\)-recoloring graph \(\mathcal{G}(G,L)\) of \(G\) is a graph whose vertices correspond to the \(L\)-colorings of \(G\) and two vertices of \(\mathcal{G}(G,L)\) are adjacent if their corresponding \(L\)-colorings differ at exactly one vertex of \(G\). A \(d\)-face in a plane graph is a face of length \(d\). Dvořák and Feghali conjectured for a planar graph \(G\) and a list assignment \(L\) of \(G\), that: (i) If \(|L(v)|\geq 10\) for every \(v\in V(G)\), then the diameter of \(\mathcal{G}(G,L)\) is \(O(|V(G)|)\). (ii) If \(G\) is triangle-free and \(|L(v)|\geq 7\) for every \(v\in V(G)\), then the diameter of \(\mathcal{G}(G,L)\) is \(O(|V(G)|)\). In a recent paper, Cranston (European J. Combin. (2022)) has proved (ii). In this paper, we prove the following results. Let \(G\) be a plane graph and \(L\) be a list assignment of \(G\). \(\bullet\) If for every \(3\)-face of \(G\), there are at most two \(3\)-faces adjacent to it and \(|L(v)|\geq 10\) for every \(v\in V(G)\), then the diameter of \(\mathcal{G}(G,L)\) is at most \(190|V(G)|\). \(\bullet\) If for every \(3\)-face of \(G\), there is at most one \(3\)-face adjacent to it and \(|L(v)|\geq 9\) for every \(v\in V(G)\), then the diameter of \(\mathcal{G}(G,L)\) is at most \(13|V(G)|\). \(\bullet\) If the faces adjacent to any \(3\)-face have length at least \(6\) and \(|L(v)|\geq 7\) for every \(v\in V(G)\), then the diameter of \(\mathcal{G}(G,L)\) is at most \(242|V(G)|\). This result strengthens the Cranston's result on (ii).