Research ArticleOpen AccessGoogle Scholar indexed
Complexity of Injective Homomorphisms to Small Tournaments, and of Injective Oriented Colourings
University of the Fraser Valley, Abbotsford, British Columbia
Acadia University, Wolfville, Nova Scotia
University of Victoria, Victoria, British Columbia
- 1 University of the Fraser Valley, Abbotsford, British Columbia
- 2 Acadia University, Wolfville, Nova Scotia
- 3 University of Victoria, Victoria, British Columbia
Open Journal of Discrete Mathematics·Volume 13 (2022)·Pages 1–15·Published 8 November 2022·DOI10.4236/ojdm.2023.131001
Copy link · social · email
Abstract
Several possible definitions of local injectivity for a homomorphism of an oriented graph G to an oriented graph H are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when G is given and H is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.
KeywordsInjective Graph HomomorphismOriented ColouringComplexity
- Courcelle, B. (1994) The Monadic Second Order Logic of Graphs VI: On Several Representations of Graphs by Relational Structures. Discrete Applied Mathematics, 54, 117-149. https://doi.org/10.1016/0166-218X(94)90019-1
- MacGillivray, G., Raspaud, A. and Swarts, J. (2009) Injective Oriented Colourings. Graph Theoretic Concepts in Computer Science, 35th International Workshop WG, Lecture Notes in Computer Science, Vol. 5911, Montpellier, 24-26 June 2009, 262-272. https://doi.org/10.1007/978-3-642-11409-0_23
- MacGillivray, G., Raspaud, A. and Swarts, J. (2011) Obstructions to Injective Oriented Colourings. Proceedings of EuroComb 2011, Electronic Notes in Discrete Mathematics, Vol. 38, Budapest, 29 August-2 September 2011, 597-605. https://doi.org/10.1016/j.endm.2011.10.001
- MacGillivray, G., Raspaud, A. and Swarts, J. (2014) Obstructions to Locally Injective Oriented Improper Colourings. European Journal of Combinatorics, 35, 402-412. https://doi.org/10.1016/j.ejc.2013.06.023
- MacGillivray, G. and Swarts, J. (2010) The Complexity of Locally Injective Homomorphisms. Discrete Mathematics, 310, 2685-2696. https://doi.org/10.1016/j.disc.2010.03.034
- Swarts, J. (2008) The Complexity of Digraph Homomorphisms: Local Tournaments, Injective Homomorphisms and Polymorphisms. Ph.D. Thesis, University of Victoria, Victoria.
- Campbell, R.J. (2009) Reflexive Injective Oriented Colourings. M.Sc. Thesis, University of Victoria, Victoria, BC, Canada.
- Campbell, R.J., Clarke, N. and MacGillivray, G. (2022) Obstructions to Some Injective Oriented Colourings. https://arxiv.org/abs/2207.12523v1
- Hahn, G., Kratochvil, J., Širáň, J. and Sotteau, D. (2002) On the Injective Chromatic Number of Graphs. Discrete Mathematics, 256, 179-192. https://doi.org/10.1016/S0012-365X(01)00466-6
- Hell, P., Raspaud, A. and Stacho, J. (2008) On Injective Colourings of Chordal Graphs. In: Laber, E.S., et al., Eds., LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science Vol. 4957, Springer, Berlin, 520-530. https://doi.org/10.1007/978-3-540-78773-0_45
- Kratochvíl, J. and Siggers, M. (2014) Locally Injective k-Colourings of Planar Graphs. Discrete Applied Mathematics, 173, 53-61. https://doi.org/10.1016/j.dam.2014.03.020
- Fiala, J. and Kratochvíl, J. (2006) Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. In: Fomin, F.V., Ed., Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 4271, Springer, Berlin, 15-26. https://doi.org/10.1007/11917496_2