Relaxed Two-Coloring of Cubic Graphs
| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Relaxed Two-Coloring of Cubic Graphs |
| Speaker: | Tibor Szabo |
| Affiliation: | ETH |
| Date: | Monday, March 20 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
A RED/BLUE coloring of a graph is called $C$-relaxed if the RED vertices form an independent set, while the BLUE vertices induce connected components of order at most $C$. We show that there exists a smallest integer $C$ such that every cubic graph is $C$-relaxed colorable. This complements the fact that for $4$-regular graphs no relaxed coloring is possible with constant component order. We also show that the problem of deciding whether a cubic graph is $i$-relaxed colorable is $NP$-complete for every $2<i<C$. Joint work with Robert Berke.