Seminár Ústavu informatiky


The Hedetniemi Conjecture in Hereditarnia

Prof. Izak Broere
Department of Mathematics and Applied Mathematics, University of Pretoria

24. júna 2014 (utorok) o 14:00


A graph property is a set of countable graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H. If such a map exists, we write G → H. Given any graph H, the hom-property → H is the set of H-colourable graphs, i.e., the set of all (countable) graphs G satisfying G → H. A graph property ℘ is of finite character if, whenever we have that H ∈ ℘ for every finite induced subgraph H of a graph G, then we have that G ∈ ℘ too. The well-known conjecture of Hedetniemi states that, for all (finite) graphs G and H, we have that χ (G × H) = min{χ (G), χ (H)}. We study the (distributive) lattice of hom-properties of finite character and discuss a number of equivalent formulations of this conjecture of Hedetniemi which can be made in terms of (amongst others) the meet-irreducibility of the hom-property → Kn of n-colourable graphs in this lattice.