Location: MF 12

Speaker: Arpan Sadhukhan (TU/e)

Title: Some results and conjectures on chromatic and dichromatic number of graphs

Abstract: 
Recently Girão et al.[Combinatorica 2023], showed that for every graph F with at least one edge, there is a constant c_F such that there are graphs of arbitrarily large chromatic number and the same clique number as F, in which every F-free induced subgraph has chromatic number at most c_F. In this talk, we prove bounds for the value of c_F, when F is a complete bipartite graph. It is known that acyclic orientations of graphs are naturally related to the chromatic number. Moreover, a common theme of the constructions in  Girão et al.[Combinatorica 2023] uses graphs that can be acyclically oriented such that between any two vertices there exists at most one directed path. We will discuss some properties and results of such orientations of graphs. Finally, we will move to the dichromatic number of graphs and give a simple proof of the existence of an infinite digraph with the number of vertices and dichromatic number both having the cardinality same as that of the real numbers. Numerous open problems will be given during the talk.