Minimum order of graphs with given coloring parameters

A complete kk-coloring of a graph G=(V,E)G=(V,E) is an assignment φ:V→{1,…,k}φ:V→{1,…,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)χ(G) and achromatic number  ψ(G)ψ(G), respectively), and the Grundy number  Γ(G)Γ(G) defined as the largest kk admitting a complete coloring φφ with exactly kk colors such that every vertex v∈Vv∈V of color φ(v)φ(v) has a neighbor of color ii for all 1≤i<φ(v)1≤i<φ(v). The inequality chain χ(G)≤Γ(G)≤ψ(G)χ(G)≤Γ(G)≤ψ(G) obviously holds for all graphs GG. A triple (f,g,h)(f,g,h) of positive integers at least 2 is called realizable if there exists a connected   graph GG with χ(G)=fχ(G)=f, Γ(G)=gΓ(G)=g, and ψ(G)=hψ(G)=h. In Chartrand et al. (2010), the list of realizable triples has been found. In this paper we determine the minimum number of vertices in a connected graph with chromatic number ff, Grundy number gg, and achromatic number hh, for all realizable triples (f,g,h)(f,g,h) of integers. Furthermore, for f=g=3f=g=3 we describe the (two) extremal graphs for each h≥6h≥6. For h∈{4,5}h∈{4,5}, there are more extremal graphs, their description is given as well.