zbMATH — the first resource for mathematics

A new characterization of graphic matroids. (English) Zbl 1170.05020
A graph is planar if and only if the dual of its cycle matroid is graphic. A result of Tutte establishes a necessary condition for a matroid to be graphic, that any cocircuit has bipartite avoidance graph. J.C. Fournier [J. Comb. Theory, Ser. B 16, 181-190 (1974; Zbl 0271.05010] proved that a matroid is graphic if and only if, for any three cocircuits \(X_1\), \(X_2\), \(X_3\) with a common element, one of them separates the other two, e.g., \(X_2 \setminus X_1\) and \(X_3 \setminus X_1\) are contained in different components of \(M \setminus X_1.\) (Necessity for cographic matroids is a consequence of the Jordan Curve Theorem.) In the paper under review, the author combines these two results to obtain necessary and sufficient conditions for a (binary) matroid to be graphic that depend only on properties of fundamental cocircuits relative to a single basis \(B\) of \(M=M(E).\) This yields a more efficient test for planarity of graphs. The precise result is: a binary matroid is graphic if and only if every fundamental cocircuit has bipartite avoidance graph and, for any three fundamental cocircuits with a point in common, one of them separates the other two. The proof is by induction, involving a careful analysis of the fundamental (bipartite) graph of \(M\) relative to \(B,\) having vertex set \(E\) and \(e \in E - B\) adjacent to \(f \in B\) when \(e\) and \(f\) lie in a circuit in \(B \cup e\).

05B35 Combinatorial aspects of matroids and geometric lattices
Full Text: DOI
[1] Bixby, R.; Cunningham, W.H., Matroids, graphs and 3-connectivity, (), 91-103
[2] Fournier, J.C., Une relation de separation entre cocircuits d’un matroide, J. combin. theory ser. B, 12, 181-190, (1974) · Zbl 0271.05010
[3] Mighton, J., Computing the Jones polynomial on bipartite graphs, J. knot theory, 10, 5, 703-710, (2001) · Zbl 0998.57026
[4] Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press · Zbl 0784.05002
[5] Tutte, W.T., An algorithm for determining whether a given binary matroid is graphic, Proc. amer. math. soc., 11, 905-917, (1960) · Zbl 0097.38905
[6] Tutte, W.T., Lectures on matroids, J. res. nat. bur. standards sect. B, 69, 1-47, (1965) · Zbl 0151.33801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.