Facial graceful coloring of plane graphs

Július Czap

Abstract. Let \(G\) be a plane graph. Two edges of \(G\) are facially adjacent if they are consecutive on the boundary walk of a face of \(G\). A facial edge coloring of \(G\) is an edge coloring such that any two facially adjacent edges receive different colors. A facial graceful \(k\)-coloring of \(G\) is a proper vertex coloring \(c:V(G)\rightarrow\{1,2,\dots,k\}\) such that the induced edge coloring \(c^{\prime}:E(G)\rightarrow\{1,2,\dots,k-1\}\) defined by \(c^{\prime(uv)}=|c(u)-c(v)|\) is a facial edge coloring. The minimum integer \(k\) for which \(G\) has a facial graceful \(k\)-coloring is denoted by \(\chi_{fg}(G)\). In this paper we prove that \(\chi_{fg}(G)\leq 14\) for every plane graph \(G\) and \(\chi_{fg}(H)\leq 9\) for every outerplane graph \(H\). Moreover, we give exact bounds for cacti and trees.

Keywords: facial edge coloring, plane graph.

Mathematics Subject Classification: 05C10, 05C15.

Full text (pdf)