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 | |
| 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: |