{
  "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 $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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.32954",
  "author_total": 3,
  "authors": [
    {
      "name": "Jørgen Bang-Jensen"
    },
    {
      "name": "Stéphane Bessy"
    },
    {
      "name": "Amadeus Reinald"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/4cjaam7qs8fse.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.32954",
  "fulltext_url": null,
  "id": "4cjaam7qs8fse",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.32954",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7223662278",
  "pdf_url": "https://arxiv.org/pdf/2610.32954",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-23",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/4cjaam7qs8fse.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:35:19Z",
      "native_id": "2610.32954",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.32954"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness",
  "title_text": "Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness",
  "type": "preprint",
  "updated_at": "2026-10-30T12:35:19Z",
  "url": "https://research.draconitic.com/paper/4cjaam7qs8fse",
  "venue": "arXiv",
  "versions": []
}