标题： 弦图的骨干着色 显示英文标题

标题： Backbone colouring of chordal graphs

摘要： 一个适当的$k$-颜色分配的图$G=(V,E)$是一个函数$c: V(G)\to \{1,\ldots,k\}$，使得$c(u)\neq c(v)$对于每条边$uv\in E(G)$。 色数$\chi(G)$是最小的$k$，使得存在一个适当的$k$-着色的$G$。 给定一个连通子图$H$的$G$，$q$-骨架$k$-着色$(G,H)$是一个适当的$k$-着色$c$的$G$，使得$\lvert c(u)-c(v)\rvert \ge q$对于每条边$uv\in E(H)$。 $q$-骨架色数${\rm BBC}_q(G,H)$是存在的最小$k$，使得存在$q$-骨架$k$-着色的$(G,H)$。 在他们具有开创性的论文中，Broersma 等人~\cite{BFGW07}询问，对于任何弦图$G$和任何支撑森林$H$的$G$，我们是否得到${\rm BBC}_2(G,H)\leq \chi(G)+O(1)$。 在本工作中，我们首先证明，只要$H$是二分图且$G$是一个每个顶点最多属于两个极大团的区间图，这就成立。 我们随后证明，这并不能扩展到以二分图作为骨架的情况，通过展示一组弦图$G$，其具有满足${\rm BBC}_2(G,H)\geq \frac{5\chi(G)}{3}$的生成二分子图$H$。然后，我们证明如果$G$是弦图且$H$具有有界的最大平均度（特别是如果$H$是一棵树），则${\rm BBC}_2(G,H)\leq \chi(G)+O(\sqrt{\chi(G)})$。 我们最后证明，当$G$是弦图且$H$是$C_4$-free 时，${\rm BBC}_2(G,H)\leq \frac{3}{2}\chi(G)+O(1)$成立。 显示英文摘要

摘要： A proper $k$-colouring of a graph $G=(V,E)$ is a function $c: V(G)\to \{1,\ldots,k\}$ such that $c(u)\neq c(v)$ for every edge $uv\in E(G)$. The chromatic number $\chi(G)$ is the minimum $k$ such that there exists a proper $k$-colouring of $G$. Given a spanning subgraph $H$ of $G$, a $q$-backbone $k$-colouring of $(G,H)$ is a proper $k$-colouring $c$ of $G$ such that $\lvert c(u)-c(v)\rvert \ge q$ for every edge $uv\in E(H)$. The $q$-backbone chromatic number ${\rm BBC}_q(G,H)$ is the smallest $k$ for which there exists a $q$-backbone $k$-colouring of $(G,H)$. In their seminal paper, Broersma et al.~\cite{BFGW07} ask whether, for any chordal graph $G$ and any spanning forest $H$ of $G$, we have that ${\rm BBC}_2(G,H)\leq \chi(G)+O(1)$. In this work, we first show that this is true as long as $H$ is bipartite and $G$ is an interval graph in which each vertex belongs to at most two maximal cliques. We then show that this does not extend to bipartite graphs as backbone by exhibiting a family of chordal graphs $G$ with spanning bipartite subgraphs $H$ satisfying ${\rm BBC}_2(G,H)\geq \frac{5\chi(G)}{3}$. Then, we show that if $G$ is chordal and $H$ has bounded maximum average degree (in particular, if $H$ is a forest), then ${\rm BBC}_2(G,H)\leq \chi(G)+O(\sqrt{\chi(G)})$. We finally show that ${\rm BBC}_2(G,H)\leq \frac{3}{2}\chi(G)+O(1)$ holds whenever $G$ is chordal and $H$ is $C_4$-free.