# 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