{"id":"arxiv/2610.32954","url":"https://arxiv.org/abs/2610.32954","tags":["cs.DS","math.CO"],"score":0,"title":"Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness","domain":"cs.DS","source":"arxiv","authors":["Jørgen Bang-Jensen","Stéphane Bessy","Amadeus Reinald"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-23","reactions":{}}