Dual-Critical Graphs -- Notes on parity constrained acyclic orientations

Zoltán Király, Sándor Kisfaludi-Bak


We define dual-critical graphs as graphs that have acyclic orientations in which the indegrees have certain parity constraints. We have very limited knowledge about the complexity of dual-criticality testing. The basic definitions show that the problem is in NP, and a result of Balázs Szegedy and Christian Szegedy [4] provides a randomized polynomial algorithm, which relies on formal matrix rank computing. It is unknown whether dual-criticality test can be done in deterministic polynomial time. Moreover, the question of being in co-NP is also open.
The first section introduces dual-critical graphs and their basic properties. We examine connectivity conditions, splitting trees, and the background of the terminology, which lies in planar dual-critical graphs. The second section deals with 3-regular graphs. The main theorem of the section shows that dual-critical graphs coincide with many graph classes when restricted to 3-regular graphs. The following subsections show further equivalences, and they yield a deterministic polynomial algorithm in the 3-regular case. The final section shows some examples of non-dual-critical graphs.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Kisfaludi-Bak, S{\'a}ndor},
TITLE = {Dual-Critical Graphs -- Notes on parity constrained acyclic orientations},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-07}

Last modification: 9.1.2018. Please email your comments to Tamás Király!