Computer Science/Discrete Mathematics Seminar I

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