Multicoloring and Mycielski construction
A \(k\)-tuple colouring of a graph \(G\) is an assignment of \(k\) distinct colours to each vertex of \(G\) so that adjacent vertices receive no colours in common. The \(k\)th chromatic number \(\chi_k(G)\) is the smallest number of colours such that \(G\) has a \(k\)-tuple colouring. In the present paper the \(k\)th chromatic number of Mycielskians of graphs (also known as cones over graphs) and of generalized Mycielskians of graphs are studied. Lower and upper bounds are given. Moreover, the fractional chromatic number of graphs \(\chi_f(G)\) of a graph \(G\) is considered. That is the infimum of all fractions \(a/b\) such that \(G\) each vertex of \(G\) is assigned a \(b\)-element subset of \(\{1,2,\dots,a\}\) in such a way that adjacent vertices are assigned disjoint subsets. Especially, \(a/b\)-colourings of generalized Mycielskians of graphs are investigated.
scientific article; zbMATH DE number 5300676