An analogue of quasi-transitivity for edge-coloured graphs
Christopher Duffy, Todd Mullen · Discussiones Mathematicae Graph Theory · 2023
We extend the notion of quasi-transitive orientations of graphs to 2edge-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.