The connected-subgraph density conjecture for r-colorings
The connected-subgraph density conjecture for r-colorings
Let be the complete graph on the positive integers. For a subgraph of , write for the upper density of its vertex set and for its strong upper density; in particular, is connected. Connected-subgraph density conjecture. For , every -coloring of contains a monochromatic connected subgraph such that
This extends the infinite analogue of Gyárfás's finite connected-subgraph theorem, proved in the paper for , and the bound is best possible when is a prime power.
Sources & referencesView supporting material
Primary source
Louis DeBiasio and Paul McKenney, “Density of monochromatic infinite subgraphs”, arXiv:1611.05423 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.