A note on compact and compact circular edge-colorings of graphs

Abstract : We study two variants of edge-coloring of edge-weighted graphs, namely compact edge-coloring and circular compact edge-coloring. First, we discuss relations between these two coloring models. We prove that every outerplanar bipartite graph admits a compact edge-coloring and that the decision problem of the existence of compact circular edge-coloring is NP-complete in general. Then we provide a polynomial time 1:5-approximation algorithm and pseudo-polynomial exact algorithm for compact circular coloring of odd cycles and prove that it is NP-hard to optimally color these graphs. Finally, we prove that if a path P2 is joined by an edge to an odd cycle then the problem of the existence of a compact circular coloring becomes NP-complete.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.161--170
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00972326
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:13:21
Dernière modification le : mercredi 29 novembre 2017 - 10:26:18
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:36:03

Fichier

526-3736-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972326, version 1

Collections

Citation

Dariusz Dereniowski, Adam Nadolski. A note on compact and compact circular edge-colorings of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.161--170. 〈hal-00972326〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

225