Article in volume
Authors:
Christopher Duffy
Department of Mathematics and Statistics
University of Saskatchewan
Title:
An analogue of quasi-transitivity for edge-coloured graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 1189-1215
Received: 2021-12-02 , Revised: 2023-02-24 , Accepted: 2023-02-24 , Available online: 2023-04-19 , https://doi.org/10.7151/dmgt.2494
Abstract:
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
References:
- 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 - J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141–161.
https://doi.org/10.1002/jgt.3190200205 - I. Beaton, D. Cox, C. Duffy and N. Zolkavich, Chromatic polynomials of $2$-edge coloured graphs (2020).
arXiv: 2007.13710 - J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).
- 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 - D. Cox and C. Duffy, Chromatic polynomials of oriented graphs, Electron. J. Combin. 26(3) (2019) #P3.55.
https://doi.org/10.37236/8240 - 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 - 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. - M.C. Golumbic, The complexity of comparability graph recognition and coloring, Computing 18 (1977) 199–208.
https://doi.org/10.1007/BF02253207 - 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 - 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 - G. Macgillivray and K. Sherk, A theory of $2$-dipath colourings, Australas. J. Combin. 60 (2014) 11–26.
- 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 - 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 - É. 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 - K. Young, $2$-Dipath and Proper $2$-Dipath Colouring (Master's Thesis, University of Victoria, 2009).
Close