Clique Immersions In Random Graphs

One of the most famous problems in graph theory is the four-color problem,which has given rise to numerous interesting new problems.Hadwiger conjectured in 1943 that the chromatic number of a graph is related to the largest clique minor it contains.This conjecture has aroused the interest of many scholars,and new results have been obtained in recent years to approach the final goal.On the other hand,Bollobás,Catlin and Erd?s considered this conjecture from a probabilistic point of view,more precisely,they used random graphs G（n,p）to prove that Hadwiger’s conjecture is correct for almost all graphs.In fact,much of the fundamental work on random graphs was done by Erd?s and Rényi.The greatest discovery of them was that with the change of the probability p,many properties of graphs appear or disappear quite suddenly.The starting point of this paper is a conjecture similar to Hadwiger’s conjecture,where in 1989 Lescure and Meyniel conjectured that the chromatic number of a graph is no more than the order of the largest clique immersion it contains.Given graphs G,H,we say the graph G contains an H-immersion rooted at R for some subset R ? V（G）if there exists an injective mapping φ:V（H）→R such that for each edge uv∈E（H）,there is a path Puv in G joining vertices φ（u）and φ（v）,and all the paths Puv,uv ∈ E（H）,are pairwise edge-disjoint.For a clique immersion,we call the number of vertices of its corresponding clique its order.Referring to the ideas of Bollobás,Catlin and Erd?s,in this paper,we study and determine the order of the largest clique immersion in random graphs G（n,p）,and the result naturally implies that the Lescure-Meyniel conjecture is correct for almost all graphs.As mentioned above,some properties in random graphs can suddenly appear or disappear as the probability changes.In this case.we use different proof methods for different probabilities p.For the proof of the upper bound,we mainly use the intermediate quantity maximum degree to assist in controlling.For the proof of the lower bound,in the case when p=p（n）=ω(（log n/n）^1/2),we consturct an auxiliary hypergraph and build the strong immersion of clique with almost perfect matching on the hypergraph;in the other case when p=p（n）=ω(（log n/n）^2/3)and p=o（log n/（?））,We make use of the concept of sublinear expander graph and determine the lower bound of the order of the largest clique immersion contained in a sublinear expander under specific properties.In this way instead of directly using the properties of the random graphs to construct the target structure.we only need to prove that the random graphs satisfy the above requirements with high probability.