The Simple Chromatic Number of (m,n)-Mixed Graphs
share
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 limited to simple cliques.
READ FULL TEXT