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