Steinberg-like theorems for backbone colouring

Description

Une fonction $f: V(G)\to \{1,\ldots,k\}$ est une $k$-coloration (propre) de $G$ si $|f (u) - f (v)|\geq 1$, pour toute ar\^ete $uv\in E(G)$. Le {\it nombre chromatique} $\chi(G)$ est le plus petit entier $k$ tel qu'il existe une $k$-coloration propre de $G$.Etant donn\'es un graphe $G$ et un sous-graphe $H$ de $G$, une $k$-coloration $q$-backbone circulaire $f$ de $(G,H)$ est une $k$-coloration de $G$ telle que $q\leq |c(u)-c(v)|\leq k-q$, pour tout ar\^ete $uv\in E(H)$. Le {\it nombre chromatique $q$-backbone circulaire} d'une paire de graphes $(G,H)$, not\'e $\CBC_q(G,H)$, est le plus petit $k$ tel que $(G,H)$ admette une $k$-coloration $q$-backbone circulaire.Steinberg a conjectur\'e que si $G$ est planaire et si $G$ ne contient pas de cycles \`a 4 ou 5 sommets, alors $\chi(G)\leq 3$. tSi cette conjecture est correcte, alors on pourrait en d\'eduire que $\CBC_2(G,H)\leq 6$, pour tout $H\subseteq G$. Dans ce papier, nous montrons que si $G$ est un graphe planaire sans cycle \`a 4 ou 5 sommets et $H\subseteq G$ est une for\^et, alors $\CBC_2(G,H)\leq 7$. Ensuite, nous prouvons que si $H\subseteq G$ est une for\^et dont toutes les composantes connexes sont des chemins, alors $\CBC_2(G,H)\leq 6$.

Additional details