Skip to main content
fix spelling
Source Link
Emil Jeřábek
  • 47.5k
  • 4
  • 150
  • 209

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by KawawarabayashiKawarabayashi, Reed, and Wollan (although I am not sure that a journal version is available yet).

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawawarabayashi, Reed, and Wollan (although I am not sure that a journal version is available yet).

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawarabayashi, Reed, and Wollan (although I am not sure that a journal version is available yet).

added 66 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawawarabayashi, Reed, and Wollan (although I am not sure that a journal version is available yet).

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawawarabayashi, Reed, and Wollan.

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawawarabayashi, Reed, and Wollan (although I am not sure that a journal version is available yet).

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a polynomial time algorithm to determine if an input $\Gamma$-labelled graph $G$ contains an $H$-minor. The case you are interested in is $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$ and $H$ equals odd-$K_5$. For signed graphs, this result was also obtained independently by Kawawarabayashi, Reed, and Wollan.