A -semicoloring of a finite graph assigns one of 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.
New to topics? Read the docs here!