Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
Preprint
Abstract
A homogeneous set of a graph $G$ is a set $X$ of vertices such that $2\le \lvert X\rvert <\lvert V(G)\rvert$ 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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Unavoidable induced subgraphs in large graphs with no homogeneous setsJournal of Combinatorial Theory, Series B, 2016
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classesAdvances in Applied Mathematics, 2015
- Two forbidden induced subgraphs and well-quasi-orderingDiscrete Mathematics, 2011
- Decomposing simple permutations, with enumerative consequencesCombinatorica, 2008
- Simple permutations: Decidability and unavoidable substructuresTheoretical Computer Science, 2008
- Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-WidthTheory of Computing Systems, 2000
- Indecomposable graphsDiscrete Mathematics, 1997
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structuresDiscrete Mathematics, 1993
- P4-trees and substitution decompositionDiscrete Applied Mathematics, 1992
- Complement reducible graphsDiscrete Applied Mathematics, 1981