×

A minimum degree condition forcing complete graph immersion. (English) Zbl 1349.05180

Summary: An immersion of a graph \(H\) into a graph \(G\) is a one-to-one mapping \(f : V (H) \rightarrow V (G)\) and a collection of edge-disjoint paths in \(G\), one for each edge of \(H\), such that the path \(P_{uv}\) corresponding to edge \(uv\) has endpoints \(f (u)\) and \(f (v)\). The immersion is strong if the paths \(P_{uv}\) are internally disjoint from \(f (V (H))\). It is proved that for every positive integer \(t\), every simple graph of minimum degree at least \(200t\) contains a strong immersion of the complete graph \(K_t\). For dense graphs one can say even more. If the graph has order \(n\) and has \(2cn^2\) edges, then there is a strong immersion of the complete graph on at least \(c^2n\) vertices in \(G\) in which each path \(P_{uv}\) is of length \(2\). As an application of these results, we resolve a problem raised by P. Seymour [personal communication] by proving that the line graph of every simple graph with average degree \(d\) has a clique minor of order at least \(cd^{3/2}\), where \(c > 0\) is an absolute constant.

For small values of \(t, 1\leq t \leq 7\), every simple graph of minimum degree at least \(t - 1\) contains an immersion of \(K_t\) [F. Lescure, H. Meyniel, Ann. Discrete Math. 41, 325–331 (1989; Zbl 0675.05026); M. DeVos et al., Ars Math. Contemp. 3, No. 2, 139–146 (2010; Zbl 1213.05137)]. We provide a general class of examples showing that this does not hold when \(t\) is large.

MSC:

05C35 Extremal problems in graph theory
05C83 Graph minors
05C76 Graph operations (line graphs, products, etc.)
05C07 Vertex degrees
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. N. Abu-Khzam and M. A. Langston: Graph coloring and the immersion order, preprint. · Zbl 1276.05042
[2] N. Alon, M. Krivelevich, B. Sudakov: Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput.12 (2003), 477-494. · Zbl 1060.05050 · doi:10.1017/S0963548303005741
[3] B. Bollobás, A. Thomason: Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs, European J. Combin.19 (1998), 883-887. · Zbl 0918.05095 · doi:10.1006/eujc.1997.0188
[4] H. D. Booth, R. Govindan, M. A. Langston and S. Ramachandramurthis: Sequential and parallel algorithms for K4-immersion testing, J. Algorithms30 (1999), 344-378. · Zbl 0923.68059 · doi:10.1006/jagm.1998.0991
[5] P. A. Catlin: A bound on the chromatic number of a graph, Discrete Math.22 (1978), 81-83. · Zbl 0374.05023 · doi:10.1016/0012-365X(78)90049-3
[6] M. DeVos, K. Kawarabayashi, B. Mohar and H. Okamura: Immersing small complete graphs, Ars Math. Contemp.3 (2010), 139-146. · Zbl 1213.05137
[7] Erdős, P., Problems and results in graph theory and combinatorial analysis, 153-163 (1979), New York
[8] M. R. Fellows and M. A. Langston: Nonconstructive tools for proving polynomial-time decidability, J. ACM35 (1998), 727-738. · Zbl 0652.68049 · doi:10.1145/44483.44491
[9] J. Fox and B. Sudakov: Dependent random choice, Random Structures and Algorithms38 (2011), 68-99. · Zbl 1215.05159 · doi:10.1002/rsa.20344
[10] H. Hadwiger: Über eine Klassi kation der Streckenkomplexe, Vierteljahrsschr. Naturforsch. Ges. Zürich88 (1943), 133-142.
[11] J. Komlós, E. Szemerédi: Topological cliques in graphs. II, Combin.Probab. Comput. 5 (1996), 79-90. · Zbl 0846.05023
[12] A. Kostochka: Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica4 (1984), 307-316. · Zbl 0555.05030 · doi:10.1007/BF02579141
[13] Lescure, F.; Meyniel, H., On a problem upon configurations contained in graphs with given chromatic number, 325-331 (1985), Amsterdam · Zbl 0675.05026
[14] L. Lovász, M. D. Plummer: Matching Theory, AMS Chelsea Publishing, Providence, RI, 2009. · Zbl 1175.05002
[15] C. St. J. A. Nash-Williams: Edge-disjoint spanning trees of finite graphs, J. London Math. Soc.36 (1961), 445-450. · Zbl 0102.38805 · doi:10.1112/jlms/s1-36.1.445
[16] N. Robertson and P. D. Seymour: Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B92 (2004), 325-357. · Zbl 1061.05088 · doi:10.1016/j.jctb.2004.08.001
[17] N. Robertson and P. D. Seymour: Graph Minors XXIII, Nash-Williams’ immersion conjecture, J. Combin. Theory Ser. B100 (2010), 181-205. · Zbl 1216.05151 · doi:10.1016/j.jctb.2009.07.003
[18] N. Robertson, P. D. Seymour and R. Thomas: Hadwiger’s conjecture for K6-free graphs, Combinatorica13 (1993), 279-361. · Zbl 0830.05028 · doi:10.1007/BF01202354
[19] P. Seymour: personal communication. · Zbl 0102.38805
[20] A. Thomason: The extremal function for complete minors, J. Combin. Theory Ser. B81 (2001), 318-338. · Zbl 1024.05083 · doi:10.1006/jctb.2000.2013
[21] W. T. Tutte: On the problem of decomposing a graph into n connected factors, J. London Math. Soc.36 (1961), 221-230. · Zbl 0096.38001 · doi:10.1112/jlms/s1-36.1.221
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.