Abstract : The Four Color Conjecture regarding planar graphs, proposed in 1852, is often regarded as one of the historically foundational problems in graph theory. From this conjecture, the notion of the chromatic number of a graph has become as arguably the most studied graph invariant in the field. In this introductory talk, I will present classical results and constructions related to the concept of chromatic number, with a focus on structural aspects. The central question I will address can be summarized as: «What does a large chromatic number reveal about the structure of a graph?»

Abstract : We review a number of results from the last few years which attempt to give precise (fine-grained) upper and lower bounds on the complexity of the Coloring problem, when measured as a function of the structure of the input graph. In order to obtain such a measure we will rely on graph-theoretic parameters, such as treewidth and its many variants, while the lower bounds will be based on fine-grained hypotheses, such as the (S)ETH. If time permits, we will also discuss how these results can be extended to more general problems, such as List Coloring and Defective Coloring. No prior knowledge of parameterized or fine-grained complexity will be assumed, the focus will be on giving an accessible self-contained exposition.

Abstract : The dichromatic number of a digraph is the minimum integer k such that the vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is equivalent to the dichromatic number of the digraph obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerning the chromatic number of undirected graphs have been generalized to digraphs via the dichromatic number. However, no concept analogous to the clique number for digraphs has been available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus, in particular, on studying the notion of Chi-boundedness.

Abstract : I will discuss various probabilistic tools/techniques (mostly from concentration) that are quite useful in many graph partitioning problems through the lens of a particular result in graph coloring, namely, the fact that triangle-free graphs require much fewer colors than the trivial bound of d+1, where d is the maximum degree. The goal of the talk is as much to give an idea on such results as to discuss under which settings these tools can be applied to obtain useful graph decompositions that could be helpful for various problems.

Abstract : A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is k-chromatic if k is the minimum number of classes in such partition, and a digraph is oriented if there is at most one arc between each pair of vertices. Clearly, the smallest k-chromatic digraph is the complete digraph on k vertices, but determining the order of the smallest k-chromatic oriented graphs is a challenging problem. It is known that the smallest 2-, 3- and 4-chromatic oriented graphs have 3, 7 and 11 vertices, respectively. In 1994, Neumann-Lara conjectured that the smallest 5-chromatic oriented graph has 17 vertices. We solve this conjecture and show that the answer is actually 19.