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