Convex Hulls and Simple Colourings in Directed and 2-edge-Coloured Graphs
share
An oriented graph (2-edge-coloured graph) is complete convex when the convex hull of every arc (edge) is the entirety of the vertex set. Here we show the problem of bounding the oriented (2-edge-coloured) chromatic number of the family of planar graphs can be restricted to bounding this parameter for the family of planar complete-convex oriented (2-edge-coloured) graphs. We fully classify complete-convex oriented and 2-edge-coloured graphs with tree-width 2. Further we show that it is NP-complete to decide if a graph is the underlying graph of a complete-convex oriented or 2-edge-coloured graph even when restricted to inputs with tree-width 4.
READ FULL TEXT