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.