Steinberg-like theorems for backbone colouring

Julio Araujo 1 Frédéric Havet 2 Mathieu Schmitt 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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$.
Type de document :
Rapport
[Research Report] RR-8641, INRIA Sophia Antipolis; INRIA. 2014


https://hal.inria.fr/hal-01088698
Contributeur : Frederic Havet <>
Soumis le : vendredi 28 novembre 2014 - 14:20:55
Dernière modification le : mercredi 14 décembre 2016 - 01:03:28

Fichier

RR-8641.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01088698, version 1

Collections

Citation

Julio Araujo, Frédéric Havet, Mathieu Schmitt. Steinberg-like theorems for backbone colouring. [Research Report] RR-8641, INRIA Sophia Antipolis; INRIA. 2014. <hal-01088698>

Partager

Métriques

Consultations de
la notice

143

Téléchargements du document

175