Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs
Room B232 IBS (기초과학연구원)A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted …