Karolina Okrasa
supervisor: Zbigniew Lonc
The k-coloring problem is, arguably, one of the best studied and well-known graph problems: given a graph G, we ask whether we can assign k colors to the vertices of a graph in a way that no two adjacent vertices receive the same color.
If we have k ≥ 3 colors, the k-coloring problem is NP-complete. This means, in particular, that we do not know any algorithm which decides whether the graph G on n vertices can be colored using k colors, and does that in time polynomial in n. However, it may happen that we want to solve our problem only for graphs G with some additional properties (e.g., planar graphs, or such that each vertex has only four neighbors). The intuition suggests that these additional information may help to solve our problem faster. Thus, we are interested in theorems characterising the structure of graphs which belong to some given graph class, as usually they show how to use our additional knowledge about G to reduce the problem to a simpler one. This, in turn, obviously helps to design effective algorithms. Moreover, we can use these theorems to solve more general problems than graph coloring: graph homomorphism problems.
In this talk I will focus on the complexity of the graph homomorphism problem when the class of input instances excludes a fixed graph as an induced subgraph.