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

Abstract

Let G be a graph with minimum degree δ(G)≥|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, proving that every graph G satisfying δ(G)≥(|V(G)|−1)/2 has a $2$-edge-coloring such that almost all pairs of vertices are connected by a rainbow path. In addition, we propose a number of related open problems.

Counting edge-colorings of a complete graph avoiding a rainbow K₄
Fabricio S. Benevides, Josefran de O. Bastos
arXiv19 Sep 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
A Clifford-index approach connecting boundary Dirac fermions to sigma-model topological terms in the periodic table of topological insulators and superconductors
Y. X. Zhao
arXiv1 Nov 2026PreprintCC BY 4.0Full textMathematical physics Condensed matterarXiv
Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
Kengo Enami, Takahiro Matsushita
arXiv26 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Optimal K_t-free list colorings and the Pollyanna property of graphs with no triangular wheel
Hongyang Wang, Rong Wu
arXiv26 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{barat2026rainbow,
  title = {{Rainbow connecting $2$-colorings of super-Dirac graphs}},
  author = {János Barát and Simona Boyadzhiyska and Andrea Freschi},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.11437},
  eprint = {2609.11437},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.11437},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Rainbow connecting $2$-colorings of super-Dirac graphs
AU  - János Barát
AU  - Simona Boyadzhiyska
AU  - Andrea Freschi
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.11437
UR  - https://arxiv.org/abs/2609.11437
AB  - Let G be a graph with minimum degree δ(G)≥|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, proving that every graph G satisfying δ(G)≥(|V(G)|−1)/2 has a $2$-edge-coloring such that almost all pairs of vertices are connected by a rainbow path. In addition, we propose a number of related open problems.
ER  -

Abstract

Related

Cite