Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
Abstract
A path or cycle in a $2$-edge-coloured graph is alternating if consecutive edges have different colours. These objects are natural analogues of paths and cycles in graphs, and even more so in digraphs. A well-studied class is that of acyclic $2$-edge-coloured graphs, that is, those forbidding alternating cycles. In particular, (acyclic) $2$-edge-coloured graphs generalize directed (acyclic) graphs (DAGs), but the complexity of problems on DAGs is much better understood than that of the corresponding problems on acyclic $2$-edge-coloured graphs. We investigate the complexity of two such problems, whose directed counterparts are well-known. Our first result is an nO(k)-time algorithm for the alternating k-linkage problem on acyclic $2$-edge-coloured graphs. This problem asks for k vertex-disjoint alternating paths joining k prescribed pairs of vertices. This generalizes the directed k-linkage algorithm for DAGs. For every fixed k, this also yields a polynomial-time algorithm for finding k internally vertex-disjoint alternating (s,t)-paths, solving an open problem by Abouelaoualim et al. from 2008. We then consider the alternating chromatic number of $2$-edge-coloured graphs, defined as the minimum number of parts in a vertex partition such that each part induces an acyclic subgraph. This notion is analogous to the dichromatic number of digraphs, where it is known that deciding dichromatic number $2$ is NP-complete even on tournaments. Our second result is that deciding alternating chromatic number $2$ is NP-complete on complete $2$-edge-coloured graphs. Equivalently, deciding whether a graph can be partitioned into two induced threshold graphs is NP-complete.
Related
- Exact three-component covers in 2-coloured random bipartite graphs
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
- Partial Airy ideals and coloured blobbed topological recursion
- Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages
- The List Total Colouring Conjecture is False
BibTeX
@misc{bangjensen2026acyclic,
title = {{Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness}},
author = {Jørgen Bang-Jensen and Stéphane Bessy and Amadeus Reinald},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32954},
eprint = {2610.32954},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32954},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
AU - Jørgen Bang-Jensen
AU - Stéphane Bessy
AU - Amadeus Reinald
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32954
UR - https://arxiv.org/abs/2610.32954
AB - A path or cycle in a $2$-edge-coloured graph is alternating if consecutive edges have different colours. These objects are natural analogues of paths and cycles in graphs, and even more so in digraphs. A well-studied class is that of acyclic $2$-edge-coloured graphs, that is, those forbidding alternating cycles. In particular, (acyclic) $2$-edge-coloured graphs generalize directed (acyclic) graphs (DAGs), but the complexity of problems on DAGs is much better understood than that of the corresponding problems on acyclic $2$-edge-coloured graphs. We investigate the complexity of two such problems, whose directed counterparts are well-known. Our first result is an n^O(k)-time algorithm for the alternating k-linkage problem on acyclic $2$-edge-coloured graphs. This problem asks for k vertex-disjoint alternating paths joining k prescribed pairs of vertices. This generalizes the directed k-linkage algorithm for DAGs. For every fixed k, this also yields a polynomial-time algorithm for finding k internally vertex-disjoint alternating (s,t)-paths, solving an open problem by Abouelaoualim et al. from 2008. We then consider the alternating chromatic number of $2$-edge-coloured graphs, defined as the minimum number of parts in a vertex partition such that each part induces an acyclic subgraph. This notion is analogous to the dichromatic number of digraphs, where it is known that deciding dichromatic number $2$ is NP-complete even on tournaments. Our second result is that deciding alternating chromatic number $2$ is NP-complete on complete $2$-edge-coloured graphs. Equivalently, deciding whether a graph can be partitioned into two induced threshold graphs is NP-complete.
ER -