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