Metraipolis › archive › dc_281b4630da77
Wild number for spanning trees in complete and complete bipartite graphs — arXiv:2610.22142
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.22142
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:34:04.542Z
- SHA-256 of the archived text
ffe26529d5dd70754012eb24914b167313a342c20e70cbfca0f58861aa53f94b- Stable URL of this page
https://metraipolis.com/documento/dc_281b4630da77
How to cite
Wild number for spanning trees in complete and complete bipartite graphs — arXiv:2610.22142 — arXiv (en), https://arxiv.org/abs/2610.22142 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_281b4630da77 (Metraipolis archive dc_281b4630da77, sha256 ffe26529d5dd70754012eb24914b167313a342c20e70cbfca0f58861aa53f94b)
BibTeX
@misc{dc281b4630da77,
title = {Wild number for spanning trees in complete and complete bipartite graphs — arXiv:2610.22142},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.22142},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_281b4630da77; sha256 ffe26529d5dd70754012eb24914b167313a342c20e70cbfca0f58861aa53f94b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22142. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given an edge-colored graph, the wild number measures how close the graph is to having a spanning tree in every color. We investigate this parameter for complete graphs and complete bipartite graphs, with particular emphasis on minimum proper colorings and equitable $2$-colorings. For complete graphs, we determine the full range of wild numbers attainable by equitable $2$-colorings and show that, although every value in this range occurs, the expected wild number of a uniformly random equitable $2$-coloring tends to $0$ as the order of the graph grows. For minimum proper colorings of $K_n$, we establish a general lower bound, determine the exact wild number for $3 \le n \le 12$, and conjecture that the lower bound is sharp for all $n$. We also develop structural conditions on ideal wild sets and use them to obtain upper bounds and analyze the performance of a natural greedy algorithm. For complete bipartite graphs, we prove a sharp upper bound for equitable $2$-colorings and determine the wild number exactly for minimum proper colorings. Finally, we apply these results to Cartesian products of complete graphs and complete bipartite graphs, obtaining lower bounds for the wild number under minimum proper and product colorings. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.22142 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T08:50:47.605Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).