Deciding parity of graph crossing number

Petr Hliněný, Carsten Thomassen

Research output: Contribution to journalJournal articleResearchpeer-review

281 Downloads (Pure)

Abstract

We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.

Original languageEnglish
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number3
Pages (from-to)1962-1965
ISSN0895-4801
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Crossing number
  • Graph
  • NP-hardness

Fingerprint

Dive into the research topics of 'Deciding parity of graph crossing number'. Together they form a unique fingerprint.

Cite this