Deciding Parity of Graph Crossing Number

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:	Structural properties, parameterized tractability and hardness in combinatorial problems