论文标题
部分可观测时空混沌系统的无模型预测
On conflict-free proper colourings of graphs without small degree vertices
论文作者
论文摘要
如果在每个顶点的附近，一个颜色完全出现一次，则将图$ g $的正确顶点着色称为无冲突，而如果至少有$ g $ g $的$ h $ conflict-fime，则无冲突。 $ g $的这种颜色的最少颜色分别表示$χ_ {\ rm pcf}（g）$和$χ_ {\ rm pcf}^h（g）$。众所周知，$χ_ {\ rm pcf}^h（g）$可以大于$（h+1）（δ+1）\ goutugy $δ$和$ h $非常接近$Δ$的图形。我们为这些参数提供了几个新的上限，这些参数对于最低度$δ$大的图形和$ h $从$δ$分离。特别是我们表明$χ_ {\ rm pcf}^h（g）\ leq（1+o（1））δ$如果$Δ\ gg \ gg \lnδ$和$ h \llδ$，以及$χ_ {\ rm pcf}（g）\ lequqΔ+o（f foroqδ+o（for for for）这些特别是指CARO，Petruševski和Škrekovski的猜想，即每一个最高度$δ\ geq 3 $的连接图$ g $的$χ_ {\ rm pcf}（g）\leqΔ+1 $，他们证明了$χ_> q _ q _ Q _ { \ left \ lfloor \ frac {5δ} {2} \ right \ rfloor $如果$δ\ geq 1 $。
A proper vertex colouring of a graph $G$ is referred to as conflict-free if in the neighbourhood of every vertex some colour appears exactly once, while it is called $h$-conflict-free if there are at least $h$ such colours for each vertex of $G$. The least numbers of colours in such colourings of $G$ are denoted $χ_{\rm pcf}(G)$ and $χ_{\rm pcf}^h(G)$, respectively. It is known that $χ_{\rm pcf}^h(G)$ can be as large as $(h+1)(Δ+1)\approx Δ^2$ for graphs with maximum degree $Δ$ and $h$ very close to $Δ$. We provide several new upper bounds for these parameters for graphs with minimum degrees $δ$ large enough and $h$ detached from $δ$. In particular we show that $χ_{\rm pcf}^h(G)\leq (1+o(1))Δ$ if $δ\gg\lnΔ$ and $h\ll δ$, and that $χ_{\rm pcf}(G)\leq Δ+O(\ln Δ)$ for regular graphs. These specifically refer to the conjecture of Caro, Petruševski and Škrekovski that $χ_{\rm pcf}(G)\leq Δ+1$ for every connected graph $G$ of maximum degree $Δ\geq 3$, towards which they proved that $χ_{\rm pcf}(G)\leq \left\lfloor\frac{5Δ}{2}\right\rfloor$ if $Δ\geq 1$.
