Geodesic
An analogue of quasi-transitivity for edge-coloured graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1189-1215 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: oriented graph, quasi-transitivity, edge colouring, uniquely quasi-transitively colourable graphs 
@article{DMGT_2024_44_3_a18,
     author = {Duffy, Christopher and Mullen, Todd},
     title = {An analogue of quasi-transitivity for edge-coloured graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1189--1215},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a18/}
}
TY  - JOUR
AU  - Duffy, Christopher
AU  - Mullen, Todd
TI  - An analogue of quasi-transitivity for edge-coloured graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1189
EP  - 1215
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a18/
LA  - en
ID  - DMGT_2024_44_3_a18
ER  - 
%0 Journal Article
%A Duffy, Christopher
%A Mullen, Todd
%T An analogue of quasi-transitivity for edge-coloured graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1189-1215
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a18/
%G en
%F DMGT_2024_44_3_a18
Duffy, Christopher; Mullen, Todd. An analogue of quasi-transitivity for edge-coloured graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1189-1215. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a18/

[1] N. Alon and T.H. Marshall, Homomorphisms of edge-colored graphs and Coxeter groups, J. Algebraic Combin. 8 (1998) 5–13. https://doi.org/10.1023/A:1008647514949

[2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141–161. https://doi.org/10.1002/jgt.3190200205

[3] I. Beaton, D. Cox, C. Duffy and N. Zolkavich, Chromatic polynomials of 2-edge coloured graphs (2020). arXiv: 2007.13710

[4] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).

[5] A. Contreras-Balbuena, H. Galeana-Sánchez and I.A. Goldfeder, Alternating Hamiltonian cycles in 2-edge-colored multigraphs, Discrete Math. Theor. Comput. Sci. 21(1) (2019) 12. https://doi.org/10.23638/DMTCS-21-1-12

[6] D. Cox and C. Duffy, Chromatic polynomials of oriented graphs, Electron. J. Combin. 26(3) (2019) #P3.55. https://doi.org/10.37236/8240

[7] H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of strong 3- quasi-transitive digraphs, Discrete Math. 310 (2010) 2495–2498. https://doi.org/10.1016/j.disc.2010.06.008

[8] Ghouilá-Houri, Caractérisation des graphes non orientés dont on peut orienter les arêtes de manière à obtenir le graphe d'une relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370–1371 https://www.sciencedirect.com/science/article/pii//0012365X9190108E.

[9] M.C. Golumbic, The complexity of comparability graph recognition and coloring, Computing 18 (1977) 199–208. https://doi.org/10.1007/BF02253207

[10] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasi-transitive digraphs, Discrete Math. 312 (2012) 2522–2530. https://doi.org/10.1016/j.disc.2012.05.005

[11] C.T. Hoàng, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Discrete Appl. Math. 55 (1994) 133–143. https://doi.org/10.1016/0166-218X(94)90004-3

[12] G. Macgillivray and K. Sherk, A theory of 2-dipath colourings, Australas. J. Combin. 60 (2014) 11–26.

[13] A. Montejano, P. Ochem, A. Pinlou, A. Raspaud and É. Sopena, Homomorphisms of 2-edge-colored graphs, Discrete Appl. Math. 158 (2010) 1365–1379. https://doi.org/10.1016/j.dam.2009.09.017

[14] A. Raspaud and É. Sopena, Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett. 51 (1994) 171–174. https://doi.org/10.1016/0020-0190(94)00088-3

[15] É. Sopena, Homomorphisms and colourings of oriented graphs: An updated survey, Discrete Math. 339 (2016) 1993–2005. https://doi.org/10.1016/j.disc.2015.03.018

[16] K. Young, 2-Dipath and Proper 2-Dipath Colouring (Master's Thesis, University of Victoria, 2009).