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

摘要

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 ) ≤ 3 r + 3 s + 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.