Seminar Calendar
for events the day of Wednesday, March 31, 2010.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
    February 2010            March 2010             April 2010
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4  5  6       1  2  3  4  5  6                1  2  3
7  8  9 10 11 12 13    7  8  9 10 11 12 13    4  5  6  7  8  9 10
14 15 16 17 18 19 20   14 15 16 17 18 19 20   11 12 13 14 15 16 17
21 22 23 24 25 26 27   21 22 23 24 25 26 27   18 19 20 21 22 23 24
28                     28 29 30 31            25 26 27 28 29 30



Wednesday, March 31, 2010

Dynamics on Networks
11:00 am   in 2 Illini Hall ,  Wednesday, March 31, 2010
 Del Edit Copy
Submitted by lerman.
 Lee DeVille (UIUC math)Markov chains, 3Abstract: Cancelled due to illness

Graph Theory and Combinatorics
4:00 pm   in 443 Altgeld Hall,  Wednesday, March 31, 2010
 Del Edit Copy
Submitted by west.
 Xuding Zhu (National Sun Yat-sen University, Kaohsiung, Taiwan)Colouring graphs with bounded generalized colouring numberAbstract: Given a graph G and a positive integer p, χp(G) is the minimum number of colours needed to colour the vertices of G so that for any i ≤ p, any subgraph H of G having tree-depth i gets at least i colours. The tree-depth of a graph H is the smallest k such that H is contained in the underlying undirected graph of the transitive closure of a branching in which every path has at most k vertices. For example, χ2 is the ordinary chromatic number, and χ3 is the star chromatic number. This talk presents an upper bound for χp(G) in terms of the k-colouring number colk(G) of G for k=2p-2. The k-colouring number is 1 plus the minimum, over all vertex orderings of G, of the maximum number of earlier vertices reachable from a single vertex v via a path of length at most k in which only the last vertex is earlier than v. For example, col1(G) is the ordinary colouring number, which is the Szekeres-Wilf upper bound on the chromatic number. Conversely, for each integer k, we also prove an upper bound for colk(G) in terms of χk+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent: a) For every positive integer p, χp(G) is bounded for G∈ K. b) For every positive integer k, colk(G) is bounded for G∈ K. Nešetřil and Ossona de Mendez proved (a) equivalent to another condition (c). We prove the equivalence of (a) and (c) directly, which gives an alternate proof of the equivalence of (a) and (c).