2023/06/13 by Sandip Das, Das, Sandip, A. Lahiri +7
Computer Science · Mathematics · #Advanced Mathematical Theories #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2306.08069
openalex publication_date 2023/06/13 · openalex created_date 2023/06/17 · openalex updated_date 2026/07/28
An (n,m)-graph is characterised by having n types of arcs and m types of edges. A homomorphism of an (n,m)-graph G to an (n,m)-graph H, is a vertex mapping that preserves adjacency, direction, and type. The (n,m)-chromatic number of G, denoted by χ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,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 χ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 χn,m(G), a result already known in the reverse direction. Furthermore, we prove that the (n,m)-chromatic number for the family of graphs with a maximum average degree less than 2+ (2)/(4(2n+m)-1), including the subfamily of planar graphs with girth at least 8(2n+m), equals 2(2n+m)+1. This improves upon previous findings, which proved the (n,m)-chromatic number for planar graphs with girth at least 10(2n+m)-4 is 2(2n+m)+1. It is established that the (n,m)-chromatic number for the family T2 of partial 2-trees is both bounded below and above by quadratic functions of (2n+m), with the lower bound being tight when (2n+m)=2. We prove 14 ≤ χ(0,3)(T2) ≤ 15 and 14 ≤ χ(1,1)(T2) ≤ 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.