Deciding Parity of Graph Crossing Number

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr THOMASSEN Carsten

Year of publication 2018
Type Article in Periodical
Magazine / Source SIAM Journal on Discrete Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
Web https://www.fi.muni.cz/~hlineny/papers/paritycross-SIAM.pdf
Doi http://dx.doi.org/10.1137/17M1137231
Keywords graph; crossing number; NP-hardness
Description We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.