2021/05/18 by Duffy, Christopher, Mullen, Todd
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2105.08676
We extend the notion of quasi-transitive orientations of graphs to 2-edge-coloured graphs. By relating quasi-transitive 2-edge-colourings to an equivalence relation on the edge set of a graph, we classify those graphs that admit a quasi-transitive 2-edge-colouring. As a contrast to Ghouilá-Houri's classification of quasi-transitively orientable graphs as comparability graphs, we find quasi-transitively 2-edge-colourable graphs do not admit a forbiddden subgraph characterization. Restricting the problem to comparability graphs, we show that the family of uniquely quasi-transitively orientable comparability graphs is exactly the family of comparabilty graphs that admit no quasi-transitive 2-edge-colouring.