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

Author: James G. Oxley
Journal: Trans. Amer. Math. Soc. 301 (1987), 63-75
MSC: Primary 05B35; Secondary 05C75
DOI: https://doi.org/10.1090/S0002-9947-1987-0879563-6
MathSciNet review: 879563
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

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 https://doi.org/10.1112/jlms/s2-19.2.193

R. E. Bixby and W. H. Cunningham, Short cocircuits in binary matroids (submitted).

Thomas H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971), 1–22. MR 288039, DOI https://doi.org/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 https://doi.org/10.1090/S0002-9947-1972-0309764-6
Beniamino Segre, Teorie combinatorie, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 7–12. Atti dei Convegni Lincei, No. 17. 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 https://doi.org/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 https://doi.org/10.1090/S0002-9947-1986-0816330-2

---, Excluding the cycle geometries of the Kuratowski graphs from binary geometries, Proc. London Math. Soc. (to appear).

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), Utilitas Math., Winnipeg, Man., 1976, pp. 463–468. Congressus Numerantium, No. XVII. MR 0444500
James G. Oxley, On $3$-connected matroids, Canadian J. Math. 33 (1981), no. 1, 20–27. MR 608851, DOI https://doi.org/10.4153/CJM-1981-003-9

---, A characterization of the ternary matroids with no $3$-minor, J. Combin. Theory Ser. B (to appear).

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 https://doi.org/10.1016/0095-8956%2880%2990075-1
P. D. Seymour, Minors of $3$-connected matroids, European J. Combin. 6 (1985), no. 4, 375–382. MR 829357, DOI https://doi.org/10.1016/S0195-6698%2885%2980051-2
W. T. Tutte, A homotopy theorem for matroids. I, II, Trans. Amer. Math. Soc. 88 (1958), 144–174. MR 101526, DOI https://doi.org/10.1090/S0002-9947-1958-0101526-0
W. T. Tutte, Connectivity in matroids, Canadian J. Math. 18 (1966), 1301–1324. MR 205880, DOI https://doi.org/10.4153/CJM-1966-129-2

P. N. Walton, Some topics in combinatorial theory, D. Phil. thesis, Oxford, 1981.

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 https://doi.org/10.1112/S0025579300009876
D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. MR 0427112