Unavoidable induced subgraphs in large graphs with no homogeneous sets

DOI10.1016/J.JCTB.2016.01.008zbMath1332.05112arXiv1504.05322OpenAlexW3098534285MaRDI QIDQ256979

Maria Chudnovsky, Ringi Kim, Sang-il Oum, P. D. Seymour

Publication date: 14 March 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey theoryinduced subgraphmodular decompositionprime graph

Mathematics Subject Classification ID

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

Related Items (7)

Resolutions of convex geometries ⋮ Unavoidable Subtournaments in Large Tournaments with No Homogeneous Sets ⋮ Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width ⋮ Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs ⋮ Jónsson posets ⋮ Well-quasi-ordering and Embeddability of Relational Structures ⋮ A Ramsey-type theorem for the matching number regarding connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unavoidable vertex-minors in large prime graphs
• Typical subgraphs of 3- and 4-connected graphs
• Graphs indecomposable with respect to the X-join
• Extension of hereditary classes with substitutions
• Unavoidable doubly connected large graphs
• Normal hypergraphs and the perfect graph conjecture

This page was built for publication: Unavoidable induced subgraphs in large graphs with no homogeneous sets