Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, December 09, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Dan Hefetz

Weighted colorings and Alon-Tarsi choosability (Part I)

Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs; the upper bound on the choice number of $G$ obtained via their method, was later coined the Alon-Tarsi number of $G$ and was denoted by $AT(G)$. In the talk I will relate this parameter to a certain weighted sum of the proper colorings of $G$. Other than the appealing notion of obtaining upper bounds on the choice number of a graph via its proper colorings (in some sense), this result has many applications. Some of them are known; for these we give unified, and often also simpler and shorter proofs; and some are new.

Most of the first talk will be devoted to introducing chromatic, choice, and Alon-Tarsi numbers of graphs. In the second talk I will state the main result and some of its applications.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login