Semicoloring
= Semicoloring
A $k$-semicoloring of a finite <graph> assigns one of $k$ colors to every <vertex> and is a proper <graph colouring> on an <induced subgraph> containing at least half the <vertices>. This is weaker than a proper coloring of the whole <graph>, and is useful as an intermediate step in a <randomized algorithm>.