Steinberg-like theorems for backbone colouring

详细信息    查看全文

• 作者：J. Araujo^a ; ^{julio@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; F. Havet^b ; ^{frederic.havet@cnrs.fr" class="auth_mail" title="E-mail the corresponding author} ; M. Schmitt^c ; ^{mathieu.schmitt@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph Colouring ; Planar Graph ; Backbone Colouring ; Steinberg's Conjecture
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：50
• 期：Complete
• 页码：223-229
• 全文大小：200 K

文摘

A function f:V(G)→{1,…,k}$f:V(G)\to \{1,\dots ,k\}$ is a (proper) k-colouring of G   if |f(u)−f(v)|≥1$|f(u)-f(v)|\ge 1$, for every edge uv∈E(G)$uv\in E(G)$. The chromatic number  χ(G)$\chi (G)$ is the smallest integer k for which there exists a proper k-colouring of G.

Given a graph G and a subgraph H of G, a circular q-backbone k-colouring c of (G, H) is a k-colouring of G   such that q≤|c(u)−c(v)|≤k−q$q\le |c(u)-c(v)|\le k-q$, for each edge uv∈E(H)$uv\in E(H)$. The circular q-backbone chromatic number of a graph pair (G, H  ), denoted CBC_q(G,H)${\mathrm{CBC}}_q(G,H)$, is the minimum k such that (G, H) admits a circular q-backbone k-colouring.

In this work, we first show that if G   is a planar graph containing no cycle on 4 or 5 vertices and H⊆G$H\subseteq G$ is a forest, then CBC₂(G,H)≤7${\mathrm{CBC}}_2(G,H)\le 7$. Then, we prove that if H⊆G$H\subseteq G$ is a forest whose connected components are paths, then CBC₂(G,H)≤6${\mathrm{CBC}}_2(G,H)\le 6$.