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:
@techreport{egres-12-07,
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 www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2012}, |
NUMBER | = | {TR-2012-07} |