|
|
|
|
|
|
|
|
Graph homomorphisms and circular chromatic number
Graph homomorphisms are adjacency-preserving maps from the vertex set of one graph to the vertex set of another. Many practical problems and graph theory problems can be conveniently expressed in the language of graph homomorphisms. By viewing graph colorings as graph homomorphisms, one obtains an interesting refinement of the chromatic number of a graph, namely the circular chromatic number. We show that circular coloring of graphs is closely related to scheduling problems in distributed computation and to other problems in computer science. We discuss the duality between circular chromatic number and circular flow number of graphs embedded in surfaces and pseudo-surfaces. We also explain the connection between such duality and some long-standing open problems concerning oriented circuit double cover.
Thursday, April 8, 2004, 243 Altgeld Hall, 2:00 p.m.
"Game chromatic number of graphs" Wed., April 7, 4 p.m., 445 Altgeld Hall
The game chromatic number of a graph $G$ is the least integer $k$ such that
Alice has a winning strategy in the following coloring game: Alice and Bob
alternately color vertices of $G$, using colors from a set of $k$ colors,
subject to the requirement that adjacent vertices cannot be colored the same
color. Alice wins the game if eventually all the vertices are colored. This
talk explains a simple but useful strategy for Alice to play the game:
the activation strategy. We shall prove some best known upper bounds for the
game chromatic number of various classes of graphs by using this strategy.
and "Complexity of graph homomorphism problems" Fri., April 9, 1 p.m., 3403 Siebel Center.
Let H be a fixed directed graph. The H-coloring problem is to determine whether or not an input digraph G admits a homomorphism to H (that is, an arc-preserving mapping from V(G) to V(H). Hell and Nesetril proved that for a symmetric digraph (that is, undirected graph) H, the H-coloring problem is polynomial if H is bipartite and is NP-complete otherwise. For a general digraph H, it is a long-standing open problem to determine the complexity of H-coloring.
We introduce the concept of bounded treewidth duality for H-coloring problems and prove that H-coloring problems with this property are polynomial-time solvable. If P\neqNP, then for symmetric directed graphs H, the H-coloring problem is polynomial-time solvable if and only if it has bounded treewidth duality. For general directed graphs, all the presently known polynomial-time solvable cases have bounded treewidth duality. This is joint work with P. Hell and J. Nesetril.