Star-chromatic number

Star-chromatic number --- звездное хроматическое число.

The star-chromatic number of a graph [math]\displaystyle{ G }[/math] (denoted [math]\displaystyle{ \chi^{\star}(G) }[/math]) is defined as

[math]\displaystyle{ \chi^{\star}(G) = \inf\{k/d: G\mbox{ has a } (k,d)-\mbox{coloring}\}. }[/math]

It is known that

[math]\displaystyle{ \chi(G) -1 \lt \chi^{\star}(G) \lt \chi(G), \mbox{ i.e., } \chi(G) = \lceil\chi^{\star}(G)\rceil, }[/math]

where [math]\displaystyle{ \chi(G) }[/math] is the chromatic number of [math]\displaystyle{ G }[/math].

Thus the chromatic number of a graph is determinated by its star-chromatic number. On the other hand, two graphs with the same chromatic number could have different star-chromatic numbers. In this sense, the star-chromatic number of a graph captures its structure more precisely than the ordinary chromatic number.