A Conjecture of Erdos (Q4222467)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1230405
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A Conjecture of Erdos |
scientific article; zbMATH DE number 1230405 |
Statements
A Conjecture of Erdos (English)
0 references
7 December 1998
0 references
monochromatic domination
0 references
conjecture of Erdős
0 references
0.8692395687103271
0 references
0.8449648022651672
0 references
0.7911314964294434
0 references
0.7754586935043335
0 references
A set of vertices \(A\) of a graph \(G\) dominates all vertices that are either in \(A\) or adjacent to a vertex in \(A\). If the edges of \(G\) are coloured, then a set \(A\) monochromatically dominates a set \(B\) if it dominates \(B\) in one of the subgraphs of \(G\) determined by the edges in one of the colours. This note discusses the following conjecture of Erdős and some generalizations. Conjecture. If the edges of a complete graph \(K_n\) are coloured with two colours, then for any positive integer \(t\), there is a set of \(t\) vertices that monochromatically dominate all but at most \(n/2^t\) of the vertices of \(K_n\).
0 references
