On 3-colorings of \(E(K_ n)\) (Q685557)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On 3-colorings of \(E(K_ n)\) |
scientific article |
Statements
On 3-colorings of \(E(K_ n)\) (English)
0 references
18 January 1994
0 references
Let \(\alpha'(G)\) be the cardinality of a maximum matching (i.e. the edge independence number) and \(c(G)\) be the maximum order of the components of a graph \(G\). Suppose the edges of the complete graph \(K_ n\) are coloured with three colours 1, 2 and 3. Let \(G_ i\) be the subgraph of \(K_ n\) induced by the set of edges coloured with colour \(i\). For integers \(s \geq 1\) and \(k \geq 2\), let \(f(s,k)\) be the least integer \(n\) such that if the edges of \(K_ n\) are coloured with colours 1, 2 and 3, then either \(\alpha' (G_ 1) \geq s\) or \(\max \bigl\{ c(G_ 2),c(G_ 3) \bigr\} \geq k\). The author proves that \(f(s,k)= \max \{s+k-1,2s\}\). From this formula we know that \(f(s,k)\) is not a Ramsey number. According to the author, the problem of determining \(f(s,k)\) was raised by Bialostocki and was communicated to him by J. Kahn.
0 references
maximum matching
0 references
complete graph
0 references
colours
0 references