Prime Labelings of Trees
A prime labeling of a graph labels its vertices bijectively with the integers from one to the number of vertices, so that adjacent vertices receive coprime labels. I prove the Entringer-Tout conjecture that every tree admits a prime labeling, extending the result of Haxell, Pikhurko, and Taraz from sufficiently large trees to all orders. My proof combines structural decompositions of trees, arithmetic organization of the labels, and matching arguments. I reduce the labeling problem to a structured bipartite matching problem by separating a small part of the tree, distributing labels…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02271
curl -X POST /api/v1/records/arxiv/2610.02271/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02271/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'