Asteroidal Chromatic Number of a Graph

Abstract

Let \( G = (V, E) \) be a connected graph. A subset \( A \) of \( V \) is called an asteroidal set if for any three vertices \( u,v,w \) in \( A \), there exists a \( u \)-\( v \) path in \( G \) that avoids the neighbourhood of \( w \). The asteroidal chromatic number \( \chi_a \) of \( G \) is the minimum order of a partition of \( V \) into asteroidal sets. In this paper we initiate a study of this parameter. We determine the value of \( \chi_a \) for several classes of graphs, obtain sharp bounds, and Nordhaus-Gaddum type results.