Deciding Parity of Graph Crossing Number
Authors | |
---|---|
Year of publication | 2018 |
Type | Article in Periodical |
Magazine / Source | SIAM Journal on Discrete Mathematics |
MU Faculty or unit | |
Citation | HLINĚNÝ, Petr and Carsten THOMASSEN. Deciding Parity of Graph Crossing Number. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2018, vol. 32, No 3, p. 1962-1965. ISSN 0895-4801. Available from: https://dx.doi.org/10.1137/17M1137231. |
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: |