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(v_{1})-f(v_{2})|≥ r for every two adjacent vertices v_{1} and v_{2}, |f(e_{1}) - f(e_{2} )| ≥ s for every two facially adjacent edges e_{1} and e_{2}, 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: |