2021/03/31 by Christopher Duffy, P D Pavan, Duffy, Christopher +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2103.17140
openalex publication_date 2021/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we consider arc criticality in colourings of oriented graphs. We study deeply critical oriented graphs, those graphs for which the removal of any arc results in a decrease of the oriented chromatic number by 2. We prove the existence of deeply critical oriented cliques of every odd order n≥ 9, closing an open question posed by Borodin et al. (Journal of Combinatorial Theory, Series B, 81(1):150-155, 2001). Additionally, we prove the non-existence of deeply critical oriented cliques among the family of circulant oriented cliques of even order.