Karolina Okrasa
supervisor: Zbigniew Lonc
A graph is a pair G=(V(G),E(G)), where V(G) is called a set of vertices of G and E(G) is some set of two-element sets of vertices of G, called edges of G. For a fixed positive integer k, a k-coloring of a graph G is a function c: V(G) -> {1,..., k}, such that c(u) ≠ c(v) for each {u, v} ∈ E(G).
For a fixed graph H=(V(H),E(H)), a homomorphism from G to H (or, in other words, an H-coloring of G) is a function h: V(G) o V(H), such that {h(u),h(v)} ∈ E(H) for each {u, v} ∈ E(G). Graph homomorphisms form a natural generalization of graph colorings: if H is a graph with k vertices and all possible edges (called a k-clique), then G admits an H-coloring if and only if it admits a k-coloring.
In my research, graph colorings and graph homomorphisms are considered mainly from the point of view of computational complexity. For example, for a fixed graph H, we study how fast we can decide if there exists a H-coloring of a given graph G.
My work is focused on the complexity of variants of graph homomorphism problems in restricted graph classes. In general, there are no known algorithms to solve most of these problems significantly faster than by a "brute force" (i.e., by enumerating all possibilities), if G is an arbitrary graph. However, the situation may change if we restrict the class of graphs G only to graphs satisfying certain properties. During the talk I will show well-known examples of such results, together with a sketch of my recent contributions to the field.