Authors:
J. Czap, S. Jendrol', P. ©ugerek, J. Valiska
Title:
Facial [r.s,t]-colorings of plane graphs
Source:
Discussiones Mathematicae Graph Theory
Received 30.10.2017, Revised 09.03.2018, Accepted 09.03.2018, doi: 10.7151/dmgt.2135

Abstract:
Let G be a plane graph. Two edges are facially adjacent in G if they are consecutive edges on the boundary walk of a face of G. Given nonnegative integers r,s, and t, a facial [r,s,t]-coloring of a plane graph G=(V,E) is a mapping f:V ∪ E → {1,...,k} such that |f(v1)-f(v2)|≥ r for every two adjacent vertices v1 and v2, |f(e1) - f(e2 )| ≥ s for every two facially adjacent edges e1 and e2, and |f(v) - f(e)| ≥ t for all pairs of incident vertices v and edges e. The facial [r,s,t]-chromatic number ‾{χ}r,s,t(G) of G is defined to be the minimum k such that G admits a facial [r,s,t]-coloring with colors 1,...,k. In this paper we show that ‾{χ}r,s,t(G)\le 3r+3s+t+1 for every plane graph G. For some triplets [r,s,t] and for some families of plane graphs this bound is improved. {Special} attention is devoted to the cases when the parameters r,s, and t are small.
Keywords:
plane graph, boundary walk, edge-coloring, vertex-coloring, total-coloring

Links:
PDF