Bicircular matroids representable over \(\mathrm{GF}(4)\) or \(\mathrm{GF}(5)\). (English) Zbl 1338.05038
Summary: Given a bicircular matroid \(B(G)\) and \(q \in \{4, 5 \}\), we characterize when the bicircular matroid \(B(G)\) is \(\mathrm{GF}(q)\)-representable by precisely describing the structure of \(G\). These descriptions yield polynomial-time algorithms with input \(G\) to certify if \(B(G)\) is or is not \(\mathrm{GF}(q)\)-representable.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
References:
| [1] | Betten, A.; Kingan, R. J.; Kingan, S. R., A note on \(GF(5)\)-representable matroids, MATCH Commun. Math. Comput. Chem., 58, 2, 511-521 (2007) · Zbl 1199.05032 |
| [2] | Coullard, Collette R.; del Greco, John G.; Wagner, Donald K., Representations of bicircular matroids, Discrete Appl. Math., 32, 3, 223-240 (1991) · Zbl 0755.05025 |
| [3] | Cunningham, William H.; Edmonds, Jack, A combinatorial decomposition theory, Canad. J. Math., 32, 3, 734-765 (1980) · Zbl 0442.05054 |
| [4] | de Sousa, J.; Welsh, D. J.A., A characterisation of binary transversal structures, J. Math. Anal. Appl., 40, 55-59 (1972) · Zbl 0197.28802 |
| [5] | Geelen, J. F.; Gerards, A. M.H.; Kapoor, A., The excluded minors for \(GF(4)\)-representable matroids, J. Combin. Theory Ser. B, 79, 2, 247-299 (2000) · Zbl 1024.05015 |
| [6] | Geelen, Jim; Gerards, Bert; Whittle, Geoff, The highly connected matroids in minor-closed classes, Ann. Comb., 19, 1, 107-123 (2015) · Zbl 1310.05044 |
| [7] | Geelen, Jim; Kung, Joseph P. S.; Whittle, Geoff, Growth rates of minor-closed classes of matroids, J. Combin. Theory Ser. B, 99, 2, 420-427 (2009) · Zbl 1229.05072 |
| [8] | Higgs, D. A., Strong maps of geometries, J. Combin. Theory, 5, 185-191 (1968) · Zbl 0164.20602 |
| [9] | Kahn, J.; Kung, J. P.S., Varieties of combinatorial geometries, Trans. Amer. Math. Soc., 271, 2, 485-499 (1982) · Zbl 0503.05010 |
| [10] | Matthews, Laurence R., Bicircular matroids, Quart. J. Math. Oxford Ser. (2), 28, 110, 213-227 (1977) · Zbl 0386.05022 |
| [11] | Oporowski, Bogdan; Oxley, James; Thomas, Robin, Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B, 57, 2, 239-257 (1993) · Zbl 0728.05041 |
| [12] | Oxley, James, (Matroid Theory. Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 21 (2011), Oxford University Press: Oxford University Press Oxford) · Zbl 1254.05002 |
| [13] | Oxley, James, On ternary transversal matroids, Discrete Math., 62, 1, 71-83 (1986) · Zbl 0624.05023 |
| [14] | Sivaraman, Vaidyanathan, Some Topics Concerning Graphs, Signed Graphs and Matroids (2013), The Ohio State University, (Doctoral Dissertation) |
| [15] | Tutte, W. T., (Connectivity in Graphs. Connectivity in Graphs, Mathematical Expositions, vol. 15 (1966), University of Toronto Press: University of Toronto Press Toronto, Ont) · Zbl 0146.45603 |
| [16] | Wagner, Donald K., Connectivity in bicircular matroids, J. Combin. Theory Ser. B, 39, 3, 308-324 (1985) · Zbl 0584.05019 |
| [17] | Zaslavsky, Thomas, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B, 47, 1, 32-52 (1989) · Zbl 0714.05057 |
| [18] | Zaslavsky, Thomas, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B, 51, 1, 46-72 (1991) · Zbl 0763.05096 |
| [19] | Zaslavsky, Thomas, Frame matroids and biased graphs, European J. Combin., 15, 3, 303-307 (1994) · Zbl 0797.05027 |
| [20] | Zaslavsky, Thomas, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B, 89, 2, 231-297 (2003) · Zbl 1031.05034 |
| [21] | Zaslavsky, Thomas, Biased graphs. VII. Contrabalance and antivoltages, J. Combin. Theory Ser. B, 97, 6, 1019-1040 (2007) · Zbl 1125.05048 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
