The indivisibility of the homogeneous K_ n-free graphs

DOI10.1016/0095-8956(89)90017-8MaRDI QIDQ1823962zbMATH OpenOpenAlexFDO

Authors Mohamed H. El-Zahar, Norbert Sauer

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0095-8956(89)90017-8

zbMATH Keywords

graph embeddinghomogeneous graphindivisible graphsquantifier block

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Graph theory (05C99)

Review text

A graph G is indivisible if for every partition of the vertex set of G into two classes R and B there is an isomorphic copy of G either in R or in B. Every homogeneous \(K_ n\)-free graph \(H_ n\), \(n\geq 3\), is indivisible. This result extends the result of \textit{P. Komjáth} and \textit{V. Rödl} [Graphs Comb. 2, 55-60 (1986; Zbl 0589.05053)] which proves that \(H_ 3\) is indivisible.

Recommendations

• On the divisibility of homogeneous hypergraphs
• scientific article; zbMATH DE number 1439504
• A universal partition result for infinite homogeneous K_n-free and related graphs
• A Ramsey theorem for countable homogeneous directed graphs
• Edge partitions of the countable triangle free homogeneous graph

Cites work

• A family of countable homogeneous graphs
• Coloring of universal graphs
• Countable Ultrahomogeneous Undirected Graphs
• Theory of relations. Transl. from the French by P. Clote

Cited in

(22)

• The Urysohn sphere is oscillation stable
• On the divisibility of homogeneous hypergraphs
• Edge partitions of the countable triangle free homogeneous graph
• Forking and dividing in Henson graphs
• Indivisible homogeneous directed graphs and a game for vertex partitions
• A note on disconnected weakly k-homogeneous graphs
• A universal partition result for infinite homogeneous K_n-free and related graphs
• The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs
• Age and weak indivisibility
• On symmetric indivisibility of countable structures
• Structural Ramsey theory of metric spaces and topological dynamics of isometry groups
• scientific article; zbMATH DE number 1439504 (Why is no real title available?)
• On the Divisibility of Homogeneous Directed Graphs
• The Ramsey theory of Henson graphs
• Ramsey theory of homogeneous structures: current trends and open problems
• Products of classes of finite structures
• Forcing with copies of the Rado and Henson graphs
• Partitions and indivisibility properties of countable dimensional vector spaces
• Exact big Ramsey degrees for finitely constrained binary free amalgamation classes
• Indivisibility for classes of graphs
• Henson graphs and Urysohn-Henson graphs as Cayley graphs
• The oscillation stability problem for the Urysohn sphere: a combinatorial approach

This page was built for publication: The indivisibility of the homogeneous \(K_ n\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823962)