{"id":"arxiv/2609.11437","url":"https://arxiv.org/abs/2609.11437","tags":["math.CO"],"score":0,"title":"Rainbow connecting $2$-colorings of super-Dirac graphs","domain":"math.CO","source":"arxiv","authors":["János Barát","Simona Boyadzhiyska","Andrea Freschi"],"reviews":0,"subject":"math.CO","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}