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
Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35, 05C75
Retrieve articles in all journals with MSC: 05B35, 05C75
Additional Information
Article copyright:
© Copyright 1987
American Mathematical Society