×

On graphic elementary lifts of graphic matroids. (English) Zbl 1491.05048

Summary: An elementary lift of a binary matroid \(M\) that arises from a binary coextension of \(M\) can easily be obtained by applying the splitting operation on \(M\). This operation on a graphic matroid may not produce a graphic matroid. We give a method to determine the forbidden minors for the class of graphic matroids \(M\) such that the splitting of \(M\) by any set of \(k\) elements is again a graphic matroid. Using this method, we obtain such minors for \(k = 2, 3, 4\). One may compute such minors for \(k \geq 5\). As a consequence, we obtain the forbidden minors for the class of graphic matroids whose all elementary lifts obtained via binary coextensions are also graphic. There are six such graphic minors.

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.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Borse, Y. M.; Shikare, M. M.; Dalvi, K. V., Excluded-minors for the class of cographic splitting matroids, Ars Comb., 115, 219-237 (2014) · Zbl 1340.05026
[2] Borse, Y. M.; Mundhe, G., Graphic and cographic Γ-extensions of binary matroids, Discuss. Math., Graph Theory, 38, 889-898 (2018) · Zbl 1392.05024
[3] Borse, Y. M.; Mundhe, G., On n-connected splitting matroids, AKCE Int. J. Graphs Comb., 16, 1, 50-56 (2019) · Zbl 1423.05035
[4] Chen, R.; Whittle, G., On recognizing frame and lifted-graphic matroids, J. Graph Theory, 87, 1, 72-76 (2018) · Zbl 1387.05037
[5] Chen, R.; Geelen, J., Infinitely many excluded minors for frame matroids and for lifted-graphic matroids, J. Comb. Theory, Ser. B, 133, 46-53 (2018) · Zbl 1397.05181
[6] Cvetkovic, D.; Petric, M., A table of connected graphs on six vertices, Discrete Math., 50, 37-49 (1984) · Zbl 0533.05052
[7] DeVos, M.; Funk, D.; Pivotto, I., When does a biased graph come from a group labelling?, Adv. Appl. Math., 61, 1-18 (2014) · Zbl 1371.05113
[8] Funk, D.; Mayhew, D., On excluded minors for classes of graphical matroids, Discrete Math., 341, 6, 1509-1522 (2018) · Zbl 1384.05143
[9] Fleischner, H., Eulerian Graphs and Related Topics Part 1, vol. 1 (1990), North Holland: North Holland Amsterdam · Zbl 0792.05091
[10] Geelen, J.; Gerards, B.; Whittle, G., Solving Rota’s conjecture, Not. Am. Math. Soc., 61, 7, 736-743 (2014) · Zbl 1338.05039
[11] Geelen, J.; Gerards, B.; Whittle, G., The highly connected matroids in minor-closed classes, Ann. Comb., 19, 1, 107-123 (2015) · Zbl 1310.05044
[12] Harary, F., Graph Theory (1988), Narosa Publishing House: Narosa Publishing House New Delhi
[13] Mills, A., On the cocircuits of a splitting matroid, Ars Comb., 89, 243-253 (2008) · Zbl 1224.05087
[14] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[15] Raghunathan, T. T.; Shikare, M. M.; Waphare, B. N., Splitting in a binary matroid, Discrete Math., 184, 267-271 (1998) · Zbl 0955.05022
[16] Ronald, C. R.; Wilson, R. J., An Atlas of Graphs (1998), Oxford University Press: Oxford University Press Oxford · Zbl 0908.05001
[17] Shikare, M. M.; Azadi, G.; Waphare, B. N., Generalized splitting operation for binary matroids and its applications, J. Indian Math. Soc., 78, 1-4, 145-154 (2011) · Zbl 1247.05054
[18] Shikare, M. M.; Waphare, B. N., Excluded-minors for the class of graphic splitting matroids, Ars Comb., 97, 111-127 (2010) · Zbl 1249.05048
[19] Shikare, M. M.; Azadi, G., Determination of the bases of a splitting matroid, Eur. J. Comb., 24, 1, 45-52 (2003) · Zbl 1014.05018
[20] Zaslavsky, T., Biased graphs. II. The three matroids, J. Comb. Theory, Ser. B, 51, 1, 46-72 (1991) · Zbl 0763.05096
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.