Deciding parity of graph crossing number

Petr Hliněný; Carsten Thomassen

doi:10.1137/17M1137231

Deciding parity of graph crossing number

Petr Hliněný, Carsten Thomassen

Department of Applied Mathematics and Computer Science

Masaryk University

Research output: Contribution to journal › Journal article › Research › peer-review

506 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 language	English
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	3
Pages (from-to)	1962-1965
ISSN	0895-4801
DOIs	https://doi.org/10.1137/17M1137231
Publication status	Published - 1 Jan 2018

Keywords

Crossing number
Graph
NP-hardness

Access to Document

10.1137/17M1137231

4Accepted author manuscript, 225 KB
17m1137231Final published version, 105 KB

OpenUrl availability

Full text

Cite this

@article{dfa856785c904d5da5e261223f6b7821,

title = "Deciding parity of graph crossing number",

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

keywords = "Crossing number, Graph, NP-hardness",

author = "Petr Hlin{\v e}n{\'y} and Carsten Thomassen",

year = "2018",

month = jan,

day = "1",

doi = "10.1137/17M1137231",

language = "English",

volume = "32",

pages = "1962--1965",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics",

number = "3",

}

TY - JOUR

T1 - Deciding parity of graph crossing number

AU - Hliněný, Petr

AU - Thomassen, Carsten

PY - 2018/1/1

Y1 - 2018/1/1

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

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

KW - Crossing number

KW - Graph

KW - NP-hardness

U2 - 10.1137/17M1137231

DO - 10.1137/17M1137231

M3 - Journal article

AN - SCOPUS:85053940046

SN - 0895-4801

VL - 32

SP - 1962

EP - 1965

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Deciding parity of graph crossing number

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this