Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 15.02.2007 at 12:20 in S5, there is the following noon lecture:

Edge Colourings of Graphs

Michael Stiebitz

Technische Universitaet Ilmenau

Abstract

The chromatic index \chi'(G) of a (multi)graph G is the minimum number of colours needed to colour the edges of G such that adjacent edges receive distinct colours. The edge colouring problem is known to be NP-hard. For the chromatic index of G there are two natural lower bounds. On the one hand, \chi'(G) ≥ \Delta(G) where \Delta(G) is the maximum degree of $G$. On the other hand, \chi'(G)≥ \W(G) where

\W(G) =\max_{H\subseteq G}\left\lceil \frac{|E(H)|}{\lfloor \frac{1}{2}|V(H)|\rfloor} \right\rceil.

A graph G is called elementary if \chi'(G)=\W(G). Goldberg and, independently, Seymour conjectured in the 1970s that every graph G is elementary provided that \chi(G)> \Delta(G)+1. For an integer m≥ 3, let \J_m denote the class of all graphs G such that

\chi'(G)>\frac{m}{m-1}\Delta(G)+\frac{m-3}{m-1}.

Shannon's theorem

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010