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

Abstract:

Graph coloring is one of the most 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 that are 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 types of graph families are obtained, which is a natural lower bound for the chromatic number of such graphs.

Posted on Sep 4, 2024 in Seminars, SIPo (Seminario de Investigadores Postdoctorales)