On Deeply Critical Oriented Cliques

03/31/2021
by   Christopher Duffy, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset