Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.32954
curl -X POST /api/v1/records/arxiv/2610.32954/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.32954/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'