On (n, m)-chromatic numbers of graphs with bounded sparsity parameters

An (n, n , m )-graph is characterized by n types of arcs and m types of edges. A homomorphism of an (n, n , m )-graph G to an (n, n , m )-graph H , is a vertex mapping that preserves adjacency, direction, and type. The (n, n , m )-chromatic number of G , denoted by chi n , m ( G ), is the minimum value of | V ( H ) | such that there exists a homomorphism of G to H . The theory of homomorphisms of (n, n , m )-graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic, Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of G is bounded by a function of chi n , m ( G ) but not the other way around. Additionally, we show that the acyclic chromatic number of G is bounded by a function of chi n , m ( G ), a result already known in the reverse direction. Furthermore, we prove that the (n, n , m )-chromatic number for the family of graphs with maximum average degree less than 2 + 2/ 4(2n+m)-1 n + m ) - 1 , including the subfamily of planar graphs with girth at least 8(2n+m), n + m ), equals 2(2n+m)+1. n + m ) + 1. This improves upon previous findings, which proved the (n, n , m )-chromatic number for planar graphs with girth at least 10(2n n + m ) - 4 is 2(2n n + m ) + 1. It is established that the (n, n , m )-chromatic number for the family T2 2 of partial 2-trees is both bounded below and above by quadratic functions of (2n n + m ), with the lower bound being tight when (2n n + m ) = 2. We prove 14 < chi (0 , 3) (T 2 ) < 15 and 14 < chi( (1 , 1)) (T (2) ) < 21 which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof. (c) 2024 Published by Elsevier B.V.