Redicoloring some classes of circulant tournaments

2025/10/06 by Narda Cordero‐Michel, Cordero-Michel, Narda, Mika Olsen +1
Computer Science · Mathematics · #05C15 #05C20 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2510.04990

openalex publication_date 2025/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a digraph D with no loops, the dicoloring graph of D, denoted by D_k(D), is the graph whose vertices are the acyclic k-colorings of D and two colorings are adjacent in D_k(D) if they differ in color on exactly one vertex. In this paper, we prove that there is no expression ϕ(χ) in terms of the dichromatic number χ, such that the graph D_k(D) is connected for all graphs D and integers k≥ ϕ(χ). We give conditions for the dicoloring graph of two infinite families of circulant tournaments to be connected, and we provide upper bounds for its diameter. In particular, for the Payley tournament C₇(1,2,4), also known as ST₇, we prove that D_k(C₇(1,2,4)) is connected and has diameter 8, for each k≥ 3.

Citations

• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring

Related

• A Simple Construction of Tournaments with Finite and Uncountable Dichromatic Number
• Acyclic Dichromatic Number of Tournaments: these are the Champions
• A Note on the Rainbow Connectivity of Tournaments
• Coloring tournaments: from local to global
• Some results and problems on tournament structure