I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite graphs).
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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).
answered Feb 17, 2016 at 9:57
-
$\begingroup$ It is "Kawarabayashi", not "Kawawarabayashi". $\endgroup$– mathloveCommented Feb 17, 2016 at 12:16
-
$\begingroup$ @mathlove Thanks for spotting that typo. It has been edited. $\endgroup$ Commented Feb 17, 2016 at 13:03
-
$\begingroup$ @TonyHuynh, many thanks for your help! Do you know if there's some kind of generalization of Guenin's result (characterizing weakly bipartite signed graphs) to the more general setting you've looked at, with $\Gamma$-labeled graphs? $\endgroup$ Commented Mar 4, 2016 at 17:43