The Parameterized Complexity of Coloring Mixed Graphs

Antonio Lauerbach , Konstanty Junosza-Szaniawski , Marie Diana Sieper , Alexander Wolff

Authors on Pith no claims yet

Pith reviewed 2026-05-10 08:50 UTC · model grok-4.3

classification 💻 cs.CC

keywords mixedcoloringgraphsgraphdiversityneighborhoodparameterizedundirected

0 comments

The pith

Mixed graph coloring is W[1]-hard parameterized by treewidth and paraNP-hard by neighborhood diversity, but FPT parameterized by the introduced mixed neighborhood diversity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Mixed graphs have both undirected edges and directed arcs. A proper coloring requires different colors for vertices connected by an edge and strictly increasing colors along each arc. This setup generalizes ordinary graph coloring and applies to scheduling tasks that must respect ordering constraints. The authors examine how the difficulty of finding such colorings depends on structural parameters of the graph. They prove that mixed coloring remains hard even when the underlying undirected graph has small treewidth or neighborhood diversity, parameters that make ordinary coloring easy. To account for directions, they define mixed versions of neighborhood diversity and cliquewidth. With the mixed neighborhood diversity parameter the problem becomes fixed-parameter tractable. The work also considers adding transitive arcs that do not change the coloring requirements and gives tight bounds on the number of colors needed in general mixed graphs.

Core claim

Unlike classical coloring, which is 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. ... mixed coloring becomes FPT when parameterized by mixed neighborhood diversity.

Load-bearing premise

That the newly introduced mixed neighborhood diversity is a natural generalization of the undirected parameter that correctly captures the effect of arcs while remaining small enough on relevant instances to yield practical algorithms.

read the original 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)\neq 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Mixed coloring breaks standard FPT parameters like treewidth and neighborhood diversity but becomes FPT under the new mixed neighborhood diversity.

read the letter

Hi, the main point is that mixed graph coloring does not inherit the nice parameterized behavior of ordinary coloring. It is W[1]-hard parameterized by treewidth of the underlying undirected graph and paraNP-hard parameterized by neighborhood diversity. The authors restore tractability by defining mixed neighborhood diversity, which folds in the direction of arcs, and prove that coloring is FPT under this new parameter. They also give some tight chromatic-number bounds that extend earlier work on mixed interval graphs and check how transitive arcs change the parameters without changing the colorings themselves. These pieces together form a clean first classification for the problem. The hardness claims rely on standard reductions and the FPT side uses the usual dynamic-programming approach on the refined parameter, so the logic lines up with what one expects in this area. The applications to scheduling with precedence constraints are stated clearly and motivate the work without overclaiming. One soft spot is that mixed neighborhood diversity may grow quickly once arcs are present, so the FPT result could stay mostly theoretical unless the parameter stays small on the instances that actually arise in process management. The paper is short on concrete examples showing the size of the new parameter on realistic mixed graphs, which would have helped. This is aimed at people who already work on structural parameters for graph problems that mix edges and arcs. A reader who wants to see how directed constraints change complexity classifications will get direct value from the new parameters and the resulting dichotomy. It deserves a serious referee because the results are new, internally consistent, and the proofs appear to rest on established techniques. I would send it to peer review.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on standard parameterized complexity theory together with the introduction of two new graph parameters for mixed graphs. No numerical free parameters are used. The new parameters are postulated without independent evidence outside the paper.

axioms (1)

standard math Standard assumptions of parameterized complexity theory (e.g., W[1]-hardness implies no FPT algorithm unless FPT=W[1]).
Invoked to interpret the hardness results for treewidth and neighborhood diversity.

invented entities (2)

mixed neighborhood diversity no independent evidence
purpose: A structural parameter that accounts for both undirected edges and directed arcs so that mixed coloring becomes FPT.
Introduced as a natural generalization; no independent evidence provided outside the paper.
mixed cliquewidth no independent evidence
purpose: A generalization of cliquewidth to mixed graphs whose effect on mixed coloring is analyzed.
Introduced and studied but not the primary FPT parameter.

pith-pipeline@v0.9.0 · 5598 in / 1394 out tokens · 57796 ms · 2026-05-10T08:50:37.318059+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Journal of Algorithms , volume =

1 Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs.J. Algorithms, 12(2):308–340, 1991.doi:10.1016/0196-6774(91)90006-K. 2 Samuel Frederic Barr. Courcelle’s theorem: Overview and applications. Bachelor’s thesis, Oberlin College,

work page doi:10.1016/0196-6774(91)90006-k 1991
[2]

Bodlaender , title =

URL:https://digitalcommons.oberlin.edu/honors/679/. 3 Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305–1317, 1996.doi:10.1137/S0097539793251219. 4 Nicos Christofides. An algorithm for the chromatic number of a graph.Comput. J., 14(1):38–39, 1971.doi:10.1093/COMJNL/14.1.38. 5 Bruno ...

work page doi:10.1137/s0097539793251219 1996
[3]

doi:10.1007/978-3-319-21275-3. A. Lauerbach, K. Junosza-Szaniawski, M.D. Sieper, and A. Wolff 17 9 Peter Damaschke. Parameterized mixed graph coloring.J. Comb. Optim., 38(2):362–374, 2019.doi:10.1007/S10878-019-00388-Z. 10 Dominique de Werra. Restricted coloring models for timetabling.Discrete Math., 165-166:161– 170, 1997.doi:10.1016/S0012-365X(96)00208-...

work page doi:10.1007/978-3-319-21275-3 2019
[4]

17 Michael R

arXiv:1201.3091. 17 Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman,

work page arXiv
[5]

On the clique-width of some perfect graph classes

18 Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. Int. J. Foundat. Comput. Sci., 11(3):423–443, 2000.doi:10.1142/S0129054100000260. 19 Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and recognizing mixed interval graphs. In Satoru Iwat...

work page doi:10.1142/s0129054100000260 2000
[6]

21 Pierre Hansen, Julio Kuplinsky, and Dominique de Werra

doi:10.1007/978-3-031-22203-0\_30. 21 Pierre Hansen, Julio Kuplinsky, and Dominique de Werra. Mixed graph colorings.Math. Methods Oper. Res., 45(1):145–160, 1997.doi:10.1007/BF01194253. 22 Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Digraph Coloring and Distance to Acyclicity.Theory Comput. Syst., 68(4):986–1013,

work page doi:10.1007/978-3-031-22203-0 1997
[7]

23 Daniel Kobler and Udi Rotics

doi:10.1007/ s00224-022-10103-x. 23 Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique- width.Discrete Appl. Math., 126(2–3):197–221, 2003.doi:10.1016/S0166-218X(02)00198-1. 24 Marek Kubale. Interval vertex-coloring of a graph with forbidden colors.Discrete Math., 74(1–2):125–136, 1989.doi:10.1016/0012-365X(89)9020...

work page doi:10.1016/s0166-218x(02)00198-1 2003
[8]

ACM Transaction of Algorithms14(2), 13:1–13:30 (2018)

doi:10.1145/3170442. 28 Víctor Neumann-Lara. The dichromatic number of a digraph.J. Combin. Theory Ser. B, 33(3):265–270, 1982.doi:10.1016/0095-8956(82)90046-6. 18 The Parameterized Complexity of Coloring Mixed Graphs 29 Kari-Jouko Räihä and Esko Ukkonen. The shortest common supersequence problem over binary alphabet is NP-complete.Theor. Comput. Sci., 16...

work page doi:10.1145/3170442 1982
[9]

30 Bernard Ries and Dominique de Werra

doi:10.1016/ 0304-3975(81)90075-X. 30 Bernard Ries and Dominique de Werra. On two coloring problems in mixed graphs.Eur. J. Comb., 29(3):712–725, 2008.doi:10.1016/J.EJC.2007.03.006. 31 Éric Sopena. Homomorphisms and colourings of oriented graphs: An updated survey.Discrete Math., 339(7):1993–2005, 2016.doi:10.1016/j.disc.2015.03.018. 32 Yuri N. Sotskov. M...

work page doi:10.1016/j.ejc.2007.03.006 2008
[10]

doi:10.3390/math8030385. A. Lauerbach, K. Junosza-Szaniawski, M.D. Sieper, and A. Wolff 19 A Parameters The following parameters are defined for undirected graphs, and applied to mixed graphs by taking the parameter value of the underlying undirected graph. ▶ Definition 34(Vertex Cover).Avertex coverof a graph G is a set of verticesC, such that every edge...

work page doi:10.3390/math8030385