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

DOI10.1016/j.dam.2018.10.030zbMath1406.05078arXiv1607.06864OpenAlexW2510002277WikidataQ128932089 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 subgraphmodular decompositionhomogeneous setprime graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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