Rainbow connecting $2$-colorings of super-Dirac graphs
Let $G$ be a graph with minimum degree $δ(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are ``close'' to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. Surprisingly, our methods extend to a much broader class of graphs with minimum degree slightly above $|V(G)|/2$. Furthermore, we answer an asymptotic version of this question in full,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.11437
curl -X POST /api/v1/records/arxiv/2609.11437/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.11437/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'