Facial [r,s,t]-Colorings of Plane Graphs

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) ≤ 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
• 05c10
• 05c15