Indivisibility for Classes of Graphs

Abstract

We examine indivisibility for classes of graphs. We show that the class of hereditarily $\hat{I}\pm$-sparse graphs is indivisible if and only if $\hat{I}\pm >2$. Additionally, we show that the following classes of graphs are indivisible: perfect graphs, cographs, and chordal graphs, and the following classes of graphs are not indivisible: threshold graphs, split graphs, and distance-hereditary graphs.

24 pages