Minimum order of graphs with given coloring parameters
Gábor Bacsó, Piotr Borowiecki, Mihály Hujter, Źsolt Tuza · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2013
A complete $k$-coloring of a graph $G=(V,E)$ is an assignment $φ:V\to\{1,\ldots,k\}$ of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number $χ(G)$ and achromatic number $ψ(G)$, respectively), and the Grundy number $Γ(G)$ defined as the largest $k$ admitting a complete coloring $φ$ with exactly $k$ colors such that every vertex $v\in V$ of color $φ(v)$ has a neighbor of color $i$ for all $1\le i