The Parameterized Complexity of Coloring Mixed Graphs
Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff · 2026
Read The Parameterized Complexity of Coloring Mixed Graphs by Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15274.txt.
Introduction
Lauerbach and three colleagues launch a systematic study of coloring mixed graphs, which carry both undirected edges and directed arcs with ordering constraints on arc endpoints. Unlike plain coloring, the problem stays hard under treewidth and neighborhood diversity, but becomes tractable under new mixed versions of those parameters. They also give tight bounds on how many colors mixed graphs can require.
Catalog record
| CREATOR | Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107740 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15274
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Parameterized Complexity of Coloring Mixed Graphs 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 c of a mixed graph G G assigns a positive integer to each vertex such that c ( u ) ≠ c ( v ) c(u)\neq c(v) for every edge { u , v } \{u,v\} and c ( u ) < c ( v ) c(u)<c(v) for every arc ( u , v ) (u,v) of G 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 ( 𝖥𝖯𝖳 \mathsf{FPT} ) parameterized by treewidth or neighborhood diversity, we show that mixed coloring is 𝖶 [ 𝟣 ] \mathsf{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 𝖥𝖯𝖳 \mathsf{FPT} when parameterized by (the generalized) 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. Julius-Maximilians-Universität Würzburg, Germany and https://go.uniwue.de/lauerbach-antonio [email protected] https://orcid.org/0009-0007-9093-3443 Warsaw University of Technology, Polandhttps://orcid.org/0000-0003-0352-8583 Julius-Maximilians-Universität Würzburg, Germanyhttps://orcid.org/0009-0003-7491-2811 Julius-Maximilians-Universität Würzburg, Germany and https://www.informatik.uni-wuerzburg.de/en/algo/team/wolff-alexander/ https://orcid.org/0000-0001-5872-718X This work was started at the workshop Homonolo 2024 in Nová Louka. We thank the organizers and the other participants. ccs Theory of computation Parameterized complexity and exact algorithms ccs Mathematics of computing Graph coloring keywords Mixed Graphs, Coloring, Parameterized Complexity, Structural Graph Parameters † † runningauthor: A. Lauerbach, K. Junosza-Szaniawski, M. D. Sieper, and A. Wolff † † copyright: Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff 1 Introduction The problem of coloring graphs, i.e., assigning as few colors as possible to vertices of an undirected graph such that adjacent vertices receive distinct colors, is an old and extensively studied problem in graph theory with applications in various areas, such as scheduling, frequency assignment, and graph drawing [ 27 ] . An example of a scheduling problem that can be modeled using graph coloring is timetabling, where courses (vertices) need to be scheduled in certain time slots (colors) while respecting conflicts (edges), e.g., due to two courses having the same teacher or students. These types of problems are referred to as chromatic scheduling problems. In real world applications, there are usually several additional constraints, such as certain courses having to be scheduled in specific time slots, certain teachers not being available at certain times, courses using multiple consecutive time slots, or a lecture having to be held before the corresponding exercises. Thus, there exist several extensions of coloring to accommodate these additional constraints, such as using list coloring to restrict courses to certain slots [ 11 ] , or using interval coloring to enforce consecutive time slots [ 26 ] . To account for precedence constraints, for example, if a course has to be scheduled before another, Hansen et al. [ 22 ] added arcs to the graph, with the idea that the arc (u,v) expresses that u has to be scheduled before v . This leads to the notion of a mixed graph G , which consists of a set V(G) of vertices , a set E(G) of (undirected) edges , and a set A(G) of (directed) arcs . A mixed graph combines the concepts of undirected and directed graphs. We require mixed graphs to be simple , i.e., without loops and without parallel edges or arcs. A k -coloring c\colon V(G)\rightarrow\{1,\dots,k\} of a mixed graph G is proper if it holds for every edge \{u,v\}\in E(G) that c(u)\neq c(v) and it holds for every arc (u,v)\in A(G) that c(u)<c(v) . We call the problem of deciding whether a mixed graph can be properly colored with k colors k - MixedColoring . As a mixed graph cannot be properly colored if it contains a directed cycle, we consider only mixed graphs without directed cycles. Apart from scheduling, mixed graph colorings have also been applied in graph drawing in order to compact layered orthogonal drawings [ 21 ] . See the survey by Sotskov [ 34 ] for more details and applications of mixed graph colorings. Since MixedColoring generalizes the classical Coloring problem for undirected graphs, it is also \mathsf{NP} -hard for three or more colors. As such, it is natural to study its parameterized complexity. However, to our knowledge, there has not yet been a systematic study of the parameterized complexity of MixedColoring . The only known results in this direction are an \mathsf{FPT} -algorithm parameterized by the number of edges (i.e., not counting arcs) by Hansen et al. [ 22 ] , with subsequent improvements by Damaschke [ 10 ] , as well as an \mathsf{XP} -algorithm parameterized by treewidth by Ries and de Werra [ 32 ] . Meanwhile, the parameterized complexity of Coloring has been extensively studied. On the positive side, results include the well-known dynamic program that runs in \mathcal{O}^{*}(k^{\mathsf{tw}}) time, where k is the number of colors, \mathsf{tw} is the treewidth of the graph, and the \mathcal{O}^{*} -notation hides polynomial factors. Since treewidth bounds the chromatic number of undirected graphs, this implies that Coloring is \mathsf{FPT} parameterized by treewidth. Lokshtanov et al. [ 29 ] even showed that under SETH (a hypothesis about the complexity of SAT with at most k literals per clause) there is no \mathcal{O}^{*}((k-\varepsilon)^{\mathsf{tw}}) -time algorithm for any \varepsilon>0 , i.e., the \mathcal{O}^{*}(k^{\mathsf{tw}}) algorithm is probably optimal. Further results include Coloring being \mathsf{FPT} parameterized by neighborhood diversity, as shown by Ganian [ 17 ] . On the negative side, Fomin et al. [ 15 ] showed that Coloring is \mathsf{W[1]} -hard parameterized by cliquewidth. However, Coloring still admits an \mathsf{XP} -algorithm parameterized by cliquewidth, as shown by Kobler and Rotics [ 25 ] . Further, applying Courcelle’s theorem [ 8 , 6 ] , a famous meta-theorem that yields \mathsf{FPT} -algorithms, it follows that Coloring is \mathsf{FPT} parameterized by cliquewidth plus chromatic number. Understanding the relationships between various structural graph parameters is crucial for analyzing the parameterized complexity of a problem. We say that a graph parameter \alpha (upper) bounds another parameter \beta if there exists a computable function f such that for every (mixed) graph G , it holds that \beta(G)\leqslant f(\alpha(G)) . If no such function exists, we say that \alpha does not (upper) bound \beta . If \alpha (upper) bounds \beta and \beta does not (upper) bound \alpha , we say that \alpha strictly (upper) bounds \beta . Meanwhile, if neither parameter bounds the other, we