Let \(G\) be a graph of minimum degree at least \(|V(G)|/2\). Can we color the edges of \(G\), with red and blue, so that every non-adjacent pair of vertices is connected by a path consisting of exactly one red edge and one blue edge? In this talk, we provide an affirmative answer when \(G\) is ``close'' to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. We also discuss an asymptotic version of this question and resolve it in full.
This is based on joint work with János Barát and Simona Boyadzhiyska.