The indivisibility of the homogeneous \(K_ n\)-free graphs (Q1823962)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The indivisibility of the homogeneous \(K_ n\)-free graphs |
scientific article; zbMATH DE number 4116579
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The indivisibility of the homogeneous \(K_ n\)-free graphs |
scientific article; zbMATH DE number 4116579 |
Statements
The indivisibility of the homogeneous \(K_ n\)-free graphs (English)
0 references
1989
0 references
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.
0 references
homogeneous graph
0 references
quantifier block
0 references
graph embedding
0 references
indivisible graphs
0 references
