论文标题
集团沉浸在没有固定两分图的图中
Clique immersion in graphs without fixed bipartite graph
论文作者
论文摘要
A graph $G$ contains $H$ as an \emph{immersion} if there is an injective mapping $ϕ: V(H)\rightarrow V(G)$ such that for each edge $uv\in E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $ϕ(u)$ and $ϕ(v)$, and all the paths $ p_ {uv} $，$ uv \在e（h）$中，是成对的边缘 - 偶数。哈德威格（Hadwiger）对莱斯库（Lescure）和梅尼尔（Meyniel）浸入集团的猜想的类似物，并由阿布·卡萨姆（Abu-Khzam）和兰斯顿（Langston）独立地指出，每个图$ g $都包含$ k_ {χ（g）} $作为沉浸式的。我们证明，对于任何常数$ \ varepsilon> 0 $和integers $ s，t \ ge2 $，存在$ d_0 = d_0 = d_0（\ varepsilon，s，t）$，使每个$ k_ {s，t} $ - 免费的图形$ g $ g $ g with $ d（g d_0这意味着上述猜想对于没有固定完整的两分图的图是渐近的。
A graph $G$ contains $H$ as an \emph{immersion} if there is an injective mapping $ϕ: V(H)\rightarrow V(G)$ such that for each edge $uv\in E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $ϕ(u)$ and $ϕ(v)$, and all the paths $P_{uv}$, $uv\in E(H)$, are pairwise edge-disjoint. An analogue of Hadwiger's conjecture for the clique immersions by Lescure and Meyniel, and independently by Abu-Khzam and Langston, states that every graph $G$ contains $K_{χ(G)}$ as an immersion. We prove that for any constant $\varepsilon>0$ and integers $s,t\ge2$, there exists $d_0=d_0(\varepsilon,s,t)$ such that every $K_{s,t}$-free graph $G$ with $d(G)\ge d_0$ contains a clique immersion of order $(1-\varepsilon)d(G)$. This implies that the above-mentioned conjecture is asymptotically true for graphs without a fixed complete bipartite graph.
