2018/09/12 by Christopher Duffy, Duffy, Christopher, Jarrod Pas +1
Computer Science · Mathematics · #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1809.04675
openalex publication_date 2018/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An (m,n)-mixed graph generalizes the notions of oriented graphs and edge-coloured graphs to a graph object with m arc types and n edge types. A simple colouring of such a graph is a non-trivial homomorphism to a reflexive target. We find that simple chromatic number of complete (m,n)-mixed graphs can be found in polynomial time. For planar graphs and k-trees (k ≥ 3) we find that allowing the target to be reflexive does not lower the chromatic number of the respective family of (m,n)-mixed graphs. This implies that the search for universal targets for such families may be restricted to simple cliques.