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

Date and Time: Tuesday, November 30, 2004, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Robert Berke

Relaxed Two-Coloring on Graphs

A family of graphs is said to be relaxed two-colorable if any of its members admits a partition into an independent set and another set inducing components of order at most C, where C is some constant. We show that any graph of maximum degree at most 3 is relaxed two-colorable. On the other hand we also show that for any constant C' there exists a 4-regular graph, such that for any partition of its vertex set into two parts with one part being independent implies that the other part spans a component of order greater than C'.

(Joint work with Tibor Szabó)

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