An overview of some coloring parameters for (n,m)-graphs

Graph coloring is one of the famous problems in graph theory. The most natural question to ask in this framework is whether or not a given family of graphs has a finite chromatic number. As graph homomorphisms generalize coloring, we study the notion of homomorphisms for (n,m)-graphs. Due to their various types of adjacencies, the (n,m)-graphs manage to capture complex relational structures and are useful for mathematical modeling. For instance, the Query Evaluation Problem (QEP) in graph databases, the immensely popular databases now used to handle highly interrelated data in social networks like Facebook, Twitter, etc., is modeled on homomorphisms of (n,m)-graphs.

This talk aims to introduce (n,m)-graphs and discuss some rigid sub-graphs of (n,m)-graphs in the context of coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these sub-graphs for various graph families are obtained, which is a natural lower bound for the chromatic number of such graphs