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

About

• Item ORO ID
• 57718
• Item Type
• Journal Item
• ISSN
• 0166-218X
• Keywords
• Modular decomposition; Induced subgraph; Prime graph; Homogeneous set
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2018 Elsevier
• Depositing User
• Robert Brignall