Complexity of $(p,1)$-Total Labelling

Frédéric Havet 1 Stéphan Thomassé 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $\{0,\dots ,l\}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The minimum $l$ for which $G$ admits a $(p,1)$-total labelling is denoted by $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to calculate even for cubic bipartite graphs~\cite{MDSA94}. We assume $p\geq 2$ in this paper. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2009, 157, pp.2859-2870
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432700
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:13:39
Dernière modification le : mardi 21 novembre 2017 - 01:23:43
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:28:13

Fichier

complexityp1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00432700, version 1

Collections

Citation

Frédéric Havet, Stéphan Thomassé. Complexity of $(p,1)$-Total Labelling. Discrete Applied Mathematics, Elsevier, 2009, 157, pp.2859-2870. 〈lirmm-00432700〉

Partager

Métriques

Consultations de la notice

370

Téléchargements de fichiers

182