Exactly Colored Complete Subgraphs of Infinite Graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914179563126784 |
|---|---|
| author | Ranđelović, Žarko |
| author_facet | Ranđelović, Žarko |
| contents | Given integers $m\le c$ and an exact $c$-coloring of the edges of a complete countably infinite graph (i.e. a coloring that uses exactly $c$ colors), must there be an infinite subgraph that is exactly $m$-colored? Using the Infinite Ramsey Theorem It is easy to show that the statement is true if $m=1,2$ or $c$. Erickson conjectured that it is false in all other cases. Stacey and Weidl proved that for each $m\ge 3$ there is some large enough $C(m)$ such that the conjecture is true for all pairs $(c,m)$ with $c>C(m)$. The main aim of this paper is to show that for all large enough $m$ the conjecture holds for all $c>m$. This reduces the number of cases needed to fully verify the conjecture to a finite number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04233 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exactly Colored Complete Subgraphs of Infinite Graphs Ranđelović, Žarko Combinatorics 05C15, 05C55 G.2.2 Given integers $m\le c$ and an exact $c$-coloring of the edges of a complete countably infinite graph (i.e. a coloring that uses exactly $c$ colors), must there be an infinite subgraph that is exactly $m$-colored? Using the Infinite Ramsey Theorem It is easy to show that the statement is true if $m=1,2$ or $c$. Erickson conjectured that it is false in all other cases. Stacey and Weidl proved that for each $m\ge 3$ there is some large enough $C(m)$ such that the conjecture is true for all pairs $(c,m)$ with $c>C(m)$. The main aim of this paper is to show that for all large enough $m$ the conjecture holds for all $c>m$. This reduces the number of cases needed to fully verify the conjecture to a finite number. |
| title | Exactly Colored Complete Subgraphs of Infinite Graphs |
| topic | Combinatorics 05C15, 05C55 G.2.2 |
| url | https://arxiv.org/abs/2512.04233 |