Notes on a theorem of Naji
arXiv:1507.00593 · doi:10.1016/j.disc.2016.07.019
Abstract
We present a new proof of an algebraic characterization of circle graphs due to W. Naji. For bipartite graphs, Naji's theorem is equivalent to an algebraic characterization of planar matroids due to J. Geelen and B. Gerards. Naji's theorem also yields an algebraic characterization of permutation graphs.
v1: 22 pages, no figure. v2: minor improvements. 23 pages, no figure v3: minor improvements. 23 pages, no figure v4: substantial improvements reflecting reader's suggestions. 32 pages, no figure