Physical Sciences and Mathematics Commons^™

Facial Achromatic Number Of Triangulations With Given Guarding Number, Naoki Matsumoto, Yumiko Ohno

Theory and Applications of Graphs

A (not necessarily proper) k-coloring c : V(G) → {1,2,…k} of a graph G on a surface is a facial t-complete k-coloring if every t-tuple of colors appears on the boundary of some face of G. The maximum number k such that G has a facial t-complete k-coloring is called a facial t-achromatic number of G, denoted by ψ_t(G). In this paper, we investigate the relation between the facial 3-achromatic number and guarding number of triangulations on a surface, where a guarding number of a graph G embedded on a surface, …