Talk:Characterization of dual-critical graphs

Equivalent definitions -- Tamás Király 22:58, 19 November 2010 (UTC)

It has been observed by Zoltán Király that the following four definitions are equivalent for a graph [math]G=(V,E)[/math] with [math]|V|+|E|[/math] odd:

• (recursive definition) G is dual-critical if [math]|V|=1[/math] or if there is a partition [math]V=X \cup Y[/math] such that both [math]G[X][/math] and [math]G[Y][/math] are dual-critical.
• G is dual-critical if it has an acyclic orientation where the in-degree of every node except for one is odd.
• G is dual-critical if for any [math]s \in V[/math] it has an acyclic orientation where the in-degree of every node except for s is odd.
• G is dual-critical if for any set [math]T \subset V[/math] with [math]|T|+|E|[/math] even, there is an acyclic orientation of G where T is the set of nodes with odd in-degree.

blog entry -- Veghal 01:42, 11 February 2011 (UTC)

see also the discussion of this problem in Christian Szegedy's blog entry: http://szegedy.wordpress.com/2011/02/03/parity-constrained-acyclic-orientations/ , outlining the randomized algorithm of the Szegedy-Szegedy paper.