Combinatorics Seminar

presents

Minimax degrees of quadrangle-free planar graphs

Naeem Sheikh

University of Illinois at Urbana-Champaign

Abstract: The M-degree of an edge xy in a graph is the maximum of the degrees of x and y. The minimax degree of a graph G is the minimum of the M-degrees of its edges. In order to prove upper bounds on the game chromatic number, He, Hou, Lih, Shao, Wang, and Zhu showed that every planar graph G without leaves and 4-cycles has minimax degree at most 8 and gave an example of such a graph with minimax degree 3. This yields upper bounds on the game chromatic number of quadrangle-free planar graphs. We determine the maximum possible minimax degrees for planar, projective-planar and toroidal graphs without leaves and 4-cycles. In particular, for planar and projective-planar graphs this maximum is 7. This is joint work with O. Borodin, A. Kostochka and G. Yu.

Tuesday, September 25, 2007
3:00 p.m., 241 Altgeld Hall

Upcoming speakers: 10/16: Ervin Györi (Rényi Institute, Hungarian Academy of Sciences, Budapest)

Past seminars

Spring 2007, Fall 2006, Spring 2006, Fall 2005, Spring 2005,
Fall 2004, Spring 2004, Fall 2003, Spring 2003, Fall 2002,
Spring 2002, Fall 2001, Spring 2001, Fall 2000.

Contact person

Doug West

Directions

Combinatorics seminar meets every Tuesday at 3pm in 241 Altgeld Hall. Click here for further directions.