×

zbMATH — the first resource for mathematics

Obstructions to a binary matroid being graphic. (English) Zbl 1229.05074
Summary: Bixby and Cunningham showed that a 3-connected binary matroid \(M\) is graphic if and only if every element belongs to at most two non-separating cocircuits. Likewise, Lemos showed that such a matroid \(M\) is graphic if and only if it has exactly \(r(M)+1\) non-separating cocircuits. Hence the presence in \(M\) of either an element in at least three non-separating cocircuits, or of at least \(r(M)+2\) non-separating cocircuits, implies that \(M\) is non-graphic. We provide lower bounds on the size of the set of such elements, and on the number of non-separating cocircuits, in such non-graphic binary matroids. A computationally efficient method for finding such lower bounds for specific minor-closed classes of matroids is given. Applications of this method and other results on sets of obstructions to a binary matroid being graphic are given.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bixby, R.E.; Cunningham, W.H., Matroids, graphs, and 3-connectivity, (), 91-103
[2] Junior, B.M.; Lemos, M.; Melo, T.R.B., Non-separating circuits and cocircuits in matroids, (), 162-171 · Zbl 1121.05028
[3] Kelmans, A.K., Graph planarity and related topics, (), 635-667 · Zbl 0791.05028
[4] Lemos, M., Non-separating cocircuits in binary matroids, Linear algebra appl., 382, 171-178, (2004) · Zbl 1042.05025
[5] Lemos, M., A characterization of graphic matroids using non-separating cocircuits, Adv. in appl. math., 42, 75-81, (2009) · Zbl 1247.05053
[6] Lemos, M.; Melo, T.R.B., Non-separating cocircuits in matroids, Discrete appl. math., 156, 7, 1019-1024, (2008) · Zbl 1143.05016
[7] Lemos, M.; Reid, T.J.; Wu, H., Characterizing 3-connected planar graphs and graphic matroids, J. graph theory, 64, 2, 165-174, (2010) · Zbl 1231.05059
[8] McNulty, J.; Wu, H., Connected hyperplanes in binary matroids, J. combin. theory ser. B, 79, 1, 87-97, (2000) · Zbl 1027.05019
[9] Oxley, J.G., Matroid theory, (1992), Oxford Science Publications, The Clarendon Press, Oxford University Press New York · Zbl 0784.05002
[10] Seymour, P.D., Decomposition of regular matroids, J. combin. theory ser. B, 28, 3, 305-359, (1980) · Zbl 0443.05027
[11] Tutte, W.T., How to draw a graph, Proc. lond. math. soc. (3), 13, 743-767, (1963) · Zbl 0115.40805
[12] Whittle, G., Stabilizers of classes of representable matroids, J. combin. theory ser. B, 77, 1, 39-72, (1999) · Zbl 1026.05025
[13] Wu, H., On vertex-triads in 3-connected binary matroids, Combin. probab. comput., 7, 4, 485-497, (1998) · Zbl 0918.05040
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.