Speaker: Sagnik Sen
Title: Colouring oriented graphs
Abstract:
Vertex coloring of a graph $G$ with $n$-colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of $G$ to the complete graph $K_n$ of order $n$. So, in that sense, the chromatic number $\chi(G)$ of $G$ will be the order of the smallest complete graph to which $G$ admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the chromatic number $\chi(G)$ of $G$ to be the order of the smallest graph to which $G$ admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with chromatic number equal to their order. Using the notion of graph homomorphism the concept of vertex coloring can be generalized for oriented graphs, that is, directed graphs without cycles of length at most 2.
Using graph homomorphism or otherwise, researchers have defined analogous versions of different other coloring related problems and parameters, namely, cliques, edge coloring, total coloring, fractional coloring, list coloring, complete coloring etc. for oriented graphs and studied their different aspects. In this talk we will give a brief survey on homomorphism and coloring of oriented graphs, present some open questions in this domain and mention some of our results as part of it.