Facial graceful coloring of plane graphs (Q6642849)

Let \(G\) be a (simple, loopless) plane graph. Two edges of \(G\) are facially adjacent if and only if they are consecutive on the boundary walk around some face of \(G\). A facial edge colouring of \(G\) is an edge colouring of \(G\) in which any two facially adjacent edges receive different colours. A facial graceful \(k\)-colouring of \(G\) is a proper vertex colouring of \(G\) \(c:V(G)\rightarrow \{1,2,\ldots, k\}\) such that the induced edge-colouring \(c^{\prime}: E(G)\rightarrow \{1,2,\ldots, k-1\}\) given by \(c^{\prime}(uv)=\vert c(u)-c(v)\vert\) is a facial edge-colouring. The smallest \(k\) for which there is a facial graceful \(k\)-colouring of \(G\) is denoted by \(\chi_{fg}(G)\). A little thought shows that \(\chi_{fg}(G)\) is finite for a finite graph \(G\) but it is less obvious how good an upper bound one can get on \(\chi_{fg}(G)\).\N\NThe main result of the paper under review is that \(\chi_{fg}(G)\leq 14\) for every planar graph \(G\). If the graph is outerplanar, as so often we can do better: the corresponding upper bound for outerplanar graphs is \(\chi_{fg}(G)\leq 9\).\N\NA vertex colouring of a plane graph \(G\) is an \(\ell \)-facial colouring of \(G\) if any two distinct vertices in a facial walk of length \(\ell\) have distinct colours. (A 1-facial colouring is just a standard proper colouring.) A key step towards the proofs is to observe that a vertex colouring \(c\) of a planar graph \(G\) is a facial graceful colouring of \(G\) if and only if it is a \(2\)-facial colouring of \(G\) (i.e any two vertices on a facial walk of length 2 have different colours) and the non-averaging condition \(c(y)\neq (c(x)+c(z))/2\) for any two facially adjacent edges \(xy\) and \(yz\). This already hints at a link with 3-AP free sets (a subset of \(\{1,2,\ldots, n\}\) is 3-AP free if it does not contain an arithmetic progression \(\{a,a+d,a+2d\}\) of length 3 with \(d\neq 0\)), made precise in a subsequent lemma to the effect that if a 2-facial colouring uses only the colours in a 3-AP free set, it is a facial graceful colouring. The two results now follow from results of \textit{D. Král} et al. [Eur. J. Comb. 26, No. 3--4, 473--490 (2005; Zbl 1056.05063); Eur. J. Comb. 28, No. 6, 1637--1639 (2007; Zbl 1121.05048)] to the effect that every planar graph admits a 2-facial colouring with at most 8 colours, and of [\textit{M. Montassier} and \textit{A. Raspaud}, Inf. Process. Lett. 98, No. 6, 235--241 (2006; Zbl 1178.05042)] to the effect that every outerplanar graph admits a 2-facial colouring with at most 5 colours. Planar graphs with \(\chi_{fg}(G)=7\) and outerplanar graphs with \(\chi_{fg}(G)=6\) are known, but no better, so neither bound is yet known to be tight.\N\NMore precise results are obtained for cacti (connected outerplanar graphs where any two cycles have at most one vertex in common): for them \(\chi_{fg}(G)\leq 6\) and this bound is tight. Further, for trees \(\chi_{fg}(G)\leq 5\) and this bound is tight. Further results are also shown on facial graceful 3-colouring and 4-colouring of trees.