The Simple Chromatic Number of (m,n)-Mixed Graphs

MaRDI QIDQ6306649zbMATH OpenFDO

Authors Christopher Duffy, Jarrod Pas

Publication date 12 September 2018

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 ($kgeq3$) 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.

This page was built for publication: The Simple Chromatic Number of $(m,n)$-Mixed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6306649)