×

Lift-contractions. (English) Zbl 1292.05241

Summary: We introduce and study a partial order on graphs-lift-contractions. A graph \(H\) is a lift-contraction of a graph \(G\) if \(H\) can be obtained from \(G\) by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to contain every \(n\)-vertex graph as a lift-contraction and describe the structure of graphs with an excluded lift-contraction.

MSC:

05C83 Graph minors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birmelé, E.; Bondy, J.; Reed, B., Brambles, prisms and grids, (Bondy, A.; Fonlupt, J.; Fouquet, J.-L.; Fournier, J.-C.; Ramírez Alfonsín, J. L., Graph Theory in Paris. Graph Theory in Paris, Trends in Mathematics (2007), Birkhäuser: Birkhäuser Basel), 37-44 · Zbl 1120.05087
[2] Bollobás, B.; Thomason, A., Proof of a conjecture of Mader, Erdös, and Hajnal on topological complete subgraphs, European J. Combin., 19, 883-887 (1998) · Zbl 0918.05095
[3] Chun, C.; Ding, G.; Oporowski, B.; Vertigan, D. L., Unavoidable parallel minors of 4-connected graphs, J. Graph Theory, 60, 4, 313-326 (2009) · Zbl 1215.05170
[5] Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2005), Springer-Verlag) · Zbl 1074.05001
[7] Kostochka, A., Lower bounds on the Hadwiger number of graphs by their average degree, Combinatorica, 4, 307-316 (1984) · Zbl 0555.05030
[8] Lovász, On some connectivity properties of Eulerian graphs, Acta Math. Acad. Sci. Hungar., 28, 129-138 (1976) · Zbl 0337.05124
[9] Matoušek, J.; Nešetřil, J.; Thomas, R., On polynomial-time decidability of induced-minor-closed classes, Comment. Math. Univ. Carolin., 29, 4, 703-710 (1988) · Zbl 0668.68048
[10] Oporowski, B.; Oxley, J.; Thomas, R., Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B, 57, 2, 239-257 (1993) · Zbl 0728.05041
[11] Robertson, N.; Seymour, P. D., Graph minors—a survey, (Surveys in combinatorics 1985 (Glasgow, 1985). Surveys in combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser., vol. 103 (1985), Cambridge University Press: Cambridge University Press Cambridge), 153-171 · Zbl 0568.05025
[13] Thomason, A., An extremal function for contractions of graph, Math. Proc. Cambridge Philos. Soc., 95, 261-265 (1984) · Zbl 0551.05047
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.