Star coloring and tree-width of the kneser graph KG(n, 2)

Abstract

A proper coloring of the vertices of a graph G is called a star coloring if any path of length three in G is not 2-colored. The star chromatic number of G is the minimum number of colors required to obtain a star coloring of G. In this paper, we give the exact value of the star chromatic number of the Kneser graph KG(n, 2). Moreover, we obtain a lower bound and an upper bound for the tree-width of these graphs.