论文标题
线性与中心色数
Linear versus centred chromatic numbers
论文作者
论文摘要
$\DeclareMathOperator{\chicen}{χ_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{χ_{\mathrm{lin}}}$ A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a \ emph {线性着色}是一个顶点着色，其中每个（不必要的）路径都包含一个颜色唯一的顶点。对于图$ g $，中心的色度$ \ chechen（g）$和线性色度$ \ chilin（g）$分别表示$ g $的线性颜色分别为中心的线性颜色所需的最小颜色数量。从这些定义中，立即遵循$ \ chilin（g）\ le \ checen（g）$的每个图$ g $。中心的色数等同于Treedeppth，并且已经进行了广泛的研究。关于线性着色知之甚少。 Kun等人[算法83（1）]证明$ \ checen（g）\ le \ tilde {o}（\ chilin（g）^{190}）$对于任何图$ g $，并猜测为$ \ chicen（g）（g）\ le2 \ le 2 \ chilin（g）$。随后，Czerwinski等人[Sidma 35（2）]将其上限改进到$ \ checen（g）\ le \ tilde {o}（\ chilin（g）^{19}）$。两种上限的证明均依赖于在线性色度数的伪质体数上建立下限，这些伪基体数量由于其与树宽的关键关系而出现在证明中。具体而言，Kun等人证明$ k \ times k $ pseudogrids具有线性色度$ω（\ sqrt {k}）$。我们的主要贡献是在每$ k \ times k $ pseudogrid $ g $的$ \ chilin（g）\geΩ（k）$上建立一个线性色彩数字的限制。结果，我们改善了所有图表的一般绑定到$ \ checen（g）\ le \ tilde {o}（\ chilin（g）^{10}）$。此外，这种紧密的结合提供了进一步的证据，以支持Kun等人的猜想（上图），任何图的中心色数都由其线性色度数的线性函数上限。
$\DeclareMathOperator{\chicen}{χ_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{χ_{\mathrm{lin}}}$ A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a \emph{linear colouring} is a vertex colouring in which every (not-necessarily induced) path contains a vertex whose colour is unique. For a graph $G$, the centred chromatic number $\chicen(G)$ and the linear chromatic number $\chilin(G)$ denote the minimum number of distinct colours required for a centred, respectively, linear colouring of $G$. From these definitions, it follows immediately that $\chilin(G)\le \chicen(G)$ for every graph $G$. The centred chromatic number is equivalent to treedepth and has been studied extensively. Much less is known about linear colouring. Kun et al [Algorithmica 83(1)] prove that $\chicen(G) \le \tilde{O}(\chilin(G)^{190})$ for any graph $G$ and conjecture that $\chicen(G)\le 2\chilin(G)$. Their upper bound was subsequently improved by Czerwinski et al [SIDMA 35(2)] to $\chicen(G)\le\tilde{O}(\chilin(G)^{19})$. The proof of both upper bounds relies on establishing a lower bound on the linear chromatic number of pseudogrids, which appear in the proof due to their critical relationship to treewidth. Specifically, Kun et al prove that $k\times k$ pseudogrids have linear chromatic number $Ω(\sqrt{k})$. Our main contribution is establishing a tight bound on the linear chromatic number of pseudogrids, specifically $\chilin(G)\ge Ω(k)$ for every $k\times k$ pseudogrid $G$. As a consequence we improve the general bound for all graphs to $\chicen(G)\le \tilde{O}(\chilin(G)^{10})$. In addition, this tight bound gives further evidence in support of Kun et al's conjecture (above) that the centred chromatic number of any graph is upper bounded by a linear function of its linear chromatic number.
