An ( n , m ) -graph is characterized by 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 maximum average degree less than 2 + 2 4 ( 2 n + m ) − 1 , including the subfamily of planar graphs with girth at least 8 ( 2 n + m ) , equals 2 ( 2 n + m ) + 1 . This improves upon previous findings, which proved the ( n , m ) -chromatic number for planar graphs with girth at least 10 ( 2 n + m ) − 4 is 2 ( 2 n + m ) + 1 . It is established that the ( n , m ) -chromatic number for the family T 2 of partial 2-trees is both bounded below and above by quadratic functions of ( 2 n + m ) , with the lower bound being tight when ( 2 n + m ) = 2 . We prove 14 ≤ χ ( 0 , 3 ) ( T 2 ) ≤ 15 and 14 ≤ χ ( 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.

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ 2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2 r opt at any query time, where r opt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.