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

Brignall, Robert; Choi, Hojin; Jeong, Jisu and Oum, Sang-il (2019). Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs. Discrete Applied Mathematics, 257 pp. 60–66.

DOI: https://doi.org/10.1016/j.dam.2018.10.030

Abstract

A homogeneous set of a graph G is a set X of vertices such that 2≤|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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI