Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs

Abstract

A homogeneous set of a graph $G$ is a set $X$ of vertices such that $2\le |X|<|V(G)|$ and no vertex in $V(G)-X$ has both a neighbor and a non-neighbor in $X$. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.

13 pages, 5 figures. Accepted to Discrete Appl. Math

References in corpus (1)

• Unavoidable induced subgraphs in large graphs with no homogeneous sets