论文标题
不兼容系统中的图形瓷砖
Graph tilings in incompatibility systems
论文作者
论文摘要
\ emph {不兼容系统} $（g，\ mathcal {f}）$由图$ g $和一个家庭$ \ mathcal {f} = \ {f_V \} _ { {e（g）\选择2}：e \ cap e'= \ {v \} \} $。我们说，如果$ \ {e，e（g）$ emph {e，e'，e'\ in e（g）中的两个边缘\ {如果$ h $中的每对边都兼容，则$ g $的子图$ h $ is \ emph {compatible}。不兼容的系统$（g，\ mathcal {f}）$是\ emph {$δ$ bunded}，如果对于任何顶点$ v $，并且与$ v $的任何边缘$ e $事件，最多有$δ$ f_v $的$ f_v $的成员包含$ e $。该概念的一部分是由科茨格（Kotzig）于1968年引入的过渡系统的概念，并由克里维尔维奇（Krivelevich），李（Lee）和苏达科夫（Sudakov）首次提出，以研究迪拉克图的大麻的鲁棒性。 我们证明，对于任何$α> 0 $以及带有$ h $顶点的任何图$ h $，存在一个常数$μ> 0 $，以便对于任何足够大的$ n $ a \ in h \ mathbb {n} $， $δ（g）\ ge（1- \ frac {1} {χ^*（h）}+α）n $和$（g，\ m nathcal {f}）$是$μn$ b的不相容性系统关键的色度数$χ_{CR}（H）$，我们提供的二分法如Kühn-Osthus结果。此外，我们给出了$ h $的$ h $，其中存在$μn$结合的不兼容系统$（g，\ m m iathcal {f}）$与$ n \ in H \ Mathbb {n} $和$ n} $和$Δ（g）没有兼容的$ h $ -FACTOR。与Kühn和Osthus先前关于嵌入$ h $ factors的工作不同，我们的证明使用了基于晶格的吸收方法。
An \emph{incompatibility system} $(G,\mathcal{F})$ consists of a graph $G$ and a family $\mathcal{F}=\{F_v\}_{v\in V(G)}$ over $G$ with $F_v\subseteq \{\{e,e'\}\in {E(G)\choose 2}: e\cap e'=\{v\}\}$. We say that two edges $e,e'\in E(G)$ are \emph{incompatible} if $\{e,e'\}\in F_v$ for some $v\in V(G)$, and otherwise \emph{compatible}. A subgraph $H$ of $G$ is \emph{compatible} if every pair of edges in $H$ are compatible. An incompatibility system $(G,\mathcal{F})$ is \emph{$Δ$-bounded} if for any vertex $v$ and any edge $e$ incident with $v$, there are at most $Δ$ members of $F_v$ containing $e$. This notion was partly motivated by a concept of transition system introduced by Kotzig in 1968, and first formulated by Krivelevich, Lee and Sudakov to study the robustness of Hamiltonicity of Dirac graphs. We prove that for any $α>0$ and any graph $H$ with $h$ vertices, there exists a constant $μ>0$ such that for any sufficiently large $n$ with $n\in h\mathbb{N}$, if $G$ is an $n$-vertex graph with $δ(G)\ge(1-\frac{1}{χ^*(H)}+α)n$ and $(G,\mathcal{F})$ is a $μn$-bounded incompatibility system, then there exists a compatible $H$-factor in $G$, where the value $χ^*(H)$ is either the chromatic number $χ(H)$ or the critical chromatic number $χ_{cr}(H)$ and we provide a dichotomy as in the Kühn--Osthus result. Moreover, we give examples $H$ for which there exists an $μn$-bounded incompatibility system $(G, \mathcal{F})$ with $n\in h\mathbb{N}$ and $δ(G)\ge(1-\frac{1}{χ^*(H)}+\fracμ{2})n$ such that $G$ contains no compatible $H$-factor. Unlike in the previous work of Kühn and Osthus on embedding $H$-factors, our proof uses the lattice-based absorption method.
