The Open UniversitySkip to content
 

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.

Full text available as:
Full text not publicly available (Accepted Manuscript)
Due to publisher licensing restrictions, this file is not available for public download until 14 November 2019
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link: https://doi.org/10.1016/j.dam.2018.10.030
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Item
Copyright Holders: 2018 Elsevier
ISSN: 0166-218X
Keywords: Modular decomposition; Induced subgraph; Prime graph; Homogeneous set
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 57718
Depositing User: Robert Brignall
Date Deposited: 16 Nov 2018 15:34
Last Modified: 03 May 2019 21:21
URI: http://oro.open.ac.uk/id/eprint/57718
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU