An update on (n,m)-chromatic numbers
share
An (n,m)-graph is a graph with n types of arcs and m types of edges. A homomorphism of an (n,m)-graph G to another (n,m)-graph H is a vertex mapping that preserves adjacency, its direction, and its type. The minimum value of |V(H)| such that G admits a homomorphism to H is the (n,m)-chromatic number of G, denoted by _n,m(G). This parameter was introduced by Nešetřil and Raspaud (J. Comb. Theory. Ser. B 2000). In this article, we show that the arboricity of G is bounded by a function of _n,m(G), but not the other way round. We also show that acyclic chromatic number of G is bounded by a function of _n,m(G), while the other way round bound was known beforehand. Moreover, we show that (n,m)-chromatic number for the family of graphs having maximum average degree less than 2+ 2/4(2n+m)-1, which contains the family of planar graphs having girth at least 8(2n+m) as a subfamily, is equal to 2(2n+m)+1. This improves the previously known result which proved that the (n,m)-chromatic number for the family planar graphs having girth at least 10(2n+m)-4 is equal to 2(2n+m)+1. It is known that the (n,m)-chromatic number for the family of partial 2-trees bounded below and above by quadratic functions of (2n+m) and that the lower bound is tight when (2n+m)=2. We show that the lower bound is not tight when (2n+m)=3 by improving the corresponding lower bounds by one. We manage to improve some of the upper bounds in these cases as well.
READ FULL TEXT