Notes on a theorem of Naji

DOI10.1016/J.DISC.2016.07.019MaRDI QIDQ329556zbMATH OpenOpenAlexFDO

Authors L. Traldi

Publication date 21 October 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00593

zbMATH Keywords

graphic matroidcircle graphpermutation graphsplit decomposition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38)

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.

Recommendations

• A proof of a circle graph characterization
• Bipartite graphs that are not circle graphs
• Bipartite complements of circle graphs
• scientific article; zbMATH DE number 3887722
• Publication:4724662

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3606473 (Why is no real title available?)
• scientific article; zbMATH DE number 3230035 (Why is no real title available?)
• scientific article; zbMATH DE number 3361902 (Why is no real title available?)
• Bipartite graphs that are not circle graphs
• Characterizing graphic matroids by a system of linear equations
• Circle graph obstructions
• Circle graphs and monadic second-order logic
• Cycle decomposition by disjoint transpositions
• Decomposition of Directed Graphs
• Diamond-free circle graphs are Helly circle
• Distance-hereditary graphs
• Graphic presentations of isotropic systems
• Isotropic matroids. II: Circle graphs
• Isotropic matroids. III: Connectivity
• Local complementation and interlacement graphs
• Partial characterizations of circle graphs
• Practical and efficient circle graph recognition
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs

Cited in

(4)

• Some remarks on Nagumo’s theorem
• A characterization of circle graphs in terms of multimatroid representations
• Bipartite complements of circle graphs
• scientific article; zbMATH DE number 3887722 (Why is no real title available?)

This page was built for publication: Notes on a theorem of Naji

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329556)