The Parameterized Complexity of Coloring Mixed Graphs
2026-04-16 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study coloring problems in mixed graphs, which have both undirected edges and directed arcs. They extend traditional graph coloring by requiring that connected vertices have different colors and that directed arcs go from a lower to a higher color number. Unlike classical coloring, they find this problem is computationally hard for some common graph parameters like treewidth. However, by defining new parameters tailored to mixed graphs, they show the problem can be solved efficiently in some cases. They also explore how adding certain kinds of arcs affects coloring and develop new general bounds for the number of colors needed.
mixed graphgraph coloringparameterized complexitytreewidthneighborhood diversitycliquewidthFPT (fixed-parameter tractability)W[1]-hardnessparaNP-hardnesschromatic number
Authors
Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff
Abstract
A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring c of a mixed graph G assigns a positive integer to each vertex such that c(u)!=c(v) for every edge {u,v} and c(u)<c(v) for every arc (u,v) of G. As in classical coloring, the objective is to minimize the number of colors. Thus, mixed (graph) coloring generalizes classical coloring of undirected graphs and allows for more general applications, such as scheduling with precedence constraints, modeling metabolic pathways, and process management in operating systems; see a survey by Sotskov [Mathematics, 2020]. We initiate the systematic study of the parameterized complexity of mixed coloring. We focus on structural graph parameters that lie between cliquewidth and vertex cover, primarily with respect to the underlying undirected graph. Unlike classical coloring, which is fixed-parameter tractable (FPT) parameterized by treewidth or neighborhood diversity, we show that mixed coloring is W[1]-hard for treewidth and even paraNP-hard for neighborhood diversity. To utilize the directedness of arcs, we introduce and analyze natural generalizations of neighborhood diversity and cliquewidth to mixed graphs, and show that mixed coloring becomes FPT when parameterized by mixed neighborhood diversity. Further, we investigate how these parameters are affected if we add transitive arcs, which do not affect colorings. Finally, we provide tight bounds on the chromatic number of mixed graphs, generalizing known bounds on mixed interval graphs.