The binary matroids with no 4-wheel minor

Oxley, James G.

doi:10.1090/S0002-9947-1987-0879563-6

The binary matroids with no $4$-wheel minor
HTML articles powered by AMS MathViewer

by James G. Oxley PDF

Trans. Amer. Math. Soc. 301 (1987), 63-75 Request permission

Abstract:

The cycle matroids of wheels are the fundamental building blocks for the class of binary matroids. Brylawski has shown that a binary matroid has no minor isomorphic to the rank-3 wheel $M({\mathcal {W}_3})$ if and only if it is a series-parallel network. In this paper we characterize the binary matroids with no minor isomorphic to $M({\mathcal {W}_4})$. This characterization is used to solve the critical problem for this class of matroids and to extend results of Kung and Walton and Welsh for related classes of binary matroids.

References

Kenneth Baclawski and Neil L. White, Higher order independence in matroids, J. London Math. Soc. (2) 19 (1979), no. 2, 193–202. MR 533317, DOI 10.1112/jlms/s2-19.2.193

Short cocircuits in binary matroids

Thomas H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971), 1–22. MR 288039, DOI 10.1090/S0002-9947-1971-0288039-7
Thomas H. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282. MR 309764, DOI 10.1090/S0002-9947-1972-0309764-6
Beniamino Segre, Teorie combinatorie, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 7–12. MR 0434827
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
Gabriel Andrew Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960), 61–85 (German). MR 121311, DOI 10.1002/mana.19600220107
I. Heller, On linear systems with integral valued solutions, Pacific J. Math. 7 (1957), 1351–1364. MR 94381
Joseph P. S. Kung, Growth rates and critical exponents of classes of binary combinatorial geometries, Trans. Amer. Math. Soc. 293 (1986), no. 2, 837–859. MR 816330, DOI 10.1090/S0002-9947-1986-0816330-2

Excluding the cycle geometries of the Kuratowski graphs from binary geometries

U. S. R. Murty, Extremal matroids with forbidden restrictions and minors (synopsis), Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976, pp. 463–468. MR 0444500
James G. Oxley, On $3$-connected matroids, Canadian J. Math. 33 (1981), no. 1, 20–27. MR 608851, DOI 10.4153/CJM-1981-003-9

A characterization of the ternary matroids with no

-minor

W. R. H. Richardson, Decomposition of chain-groups and binary matroids, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1973), Utilitas Math., Winnipeg, Man., 1973, pp. 463–476. MR 0419273
P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359. MR 579077, DOI 10.1016/0095-8956(80)90075-1
P. D. Seymour, Minors of $3$-connected matroids, European J. Combin. 6 (1985), no. 4, 375–382. MR 829357, DOI 10.1016/S0195-6698(85)80051-2
W. T. Tutte, A homotopy theorem for matroids. I, II, Trans. Amer. Math. Soc. 88 (1958), 144–174. MR 101526, DOI 10.1090/S0002-9947-1958-0101526-0
W. T. Tutte, Connectivity in matroids, Canadian J. Math. 18 (1966), 1301–1324. MR 205880, DOI 10.4153/CJM-1966-129-2

Some topics in combinatorial theory

P. N. Walton and D. J. A. Welsh, On the chromatic number of binary matroids, Mathematika 27 (1980), no. 1, 1–9. MR 581990, DOI 10.1112/S0025579300009876
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112