|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Partitioning random graphs into monochromatic components | | Deepak Bal
; Louis DeBiasio
; | | Date: |
30 Sep 2015 | | Abstract: | ErdH{o}s, Gy’arf’as, and Pyber conjectured that every $r$-colored complete
graph can be partitioned into at most $r-1$ monochromatic components; this is a
strengthening of a conjecture of Lov’asz and Ryser in which the components are
only required to form a cover. An important partial result of Haxell and
Kohayakawa says that $r$ components suffice for sufficiently large complete
graphs.
We extend these results from the setting of complete graphs to the setting of
random graphs (and along the way, graphs with large minimum degree). In
particular, we show that $r$-colored graphs with large minimum degree have a
robust structure which gives us a partition into $r$ monochromatic components
even after deleting any subset of vertices from a special linear sized set. We
use this, together with the sparse regularity lemma, to determine the threshold
for which every $r$-coloring of $G(n,p)$ can partitioned into $r$ monochromatic
components. | | Source: | arXiv, 1509.9168 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER