Star-extremal graphs and the lexicographic product

✍ Scribed by Guogang Gao; Xuding Zhu

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 537 KB
• Volume: 152
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00311-6

✦ Synopsis

The star-chromatic number and the fractional-chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star-extremal if its star-chromatic number is equal to its fractional-chromatic number. We prove that star-extremal graphs G have the following interesting property: For an arbitrary graph H the star-chromatic number X*(G[H]) of the lexicographic product G[H] is equal to the product of X*(G) and X(H). Then we show that several classes of circulant graphs are star-extremal. Thus for these circulant graphs G and arbitrary graphs H, if x*(G) and X(H) are known then we can easily determine the starchromatic number (hence the ordinary chromatic number) of the lexicographic product G [H]. For these star-extremal circulant graphs, we also derive polynomial-time anti-clique-finding and coloring algorithms.