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

DOI10.1016/j.dam.2018.10.030zbMath1406.05078arXiv1607.06864WikidataQ128932089 ScholiaQ128932089MaRDI QIDQ1730221

Hojin Choi, Jisu Jeong, Sang-il Oum, Robert Brignall

Publication date: 11 March 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.06864

zbMATH Keywords

induced subgraph; modular decomposition; homogeneous set; prime graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unavoidable induced subgraphs in large graphs with no homogeneous sets
• All minimal prime extensions of hereditary classes of graphs
• Labelled induced subgraphs and well-quasi-ordering
• Complement reducible graphs
• \(P_ 4\)-trees and substitution decomposition
• Indecomposable graphs
• On the closure of graphs under substitution
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• Two forbidden induced subgraphs and well-quasi-ordering
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Decomposing simple permutations, with enumerative consequences
• Simple permutations: Decidability and unavoidable substructures
• Growing Without Cloning
• Graph Classes: A Survey
• Handbook of Graph Grammars and Computing by Graph Transformation
• Transitiv orientierbare Graphen