Andrea Freschi

Rainbow connecting $2$-colorings of super-Dirac graphs

Let $G$ be a graph with minimum degree $\delta(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...