On \(k\)-partite subgraphs (Q2713662)
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: On \(k\)-partite subgraphs |
scientific article; zbMATH DE number 1602789
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On \(k\)-partite subgraphs |
scientific article; zbMATH DE number 1602789 |
Statements
10 June 2001
0 references
multipartite graphs
0 references
subgraphs
0 references
hypergraphs
0 references
On \(k\)-partite subgraphs (English)
0 references
It is shown that every graph \(G\) with \(\binom {kn}{2}\) edges contains a \(k\)-partite subgraph with \(\binom {k}{2}n^2\) edges. It is quoted that this result was independently proved by \textit{N. Alon} [Combinatorica 16, No. 3, 301-311 (1996; Zbl 0860.05043)]. Lower bounds on the size of a largest \(k\)-partite subhypergraph of a given \(k\)-uniform hypergraph in terms of its strong chromatic number are given.
0 references
