Proper orientation of cacti

Julio Araujo 1 Frédéric Havet 2 Claudia Linhares Sales 1 Ana Silva 1
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 : An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number − → χ (G) of a graph G is the minimum maximum in-degree of a proper orientation of G. In [1], the authors ask whether the proper orientation number of a planar graph is bounded. We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 639, pp.14-25. 〈10.1016/j.tcs.2016.05.016〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01338646
Contributeur : Frederic Havet <>
Soumis le : mercredi 29 juin 2016 - 00:49:26
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : vendredi 30 septembre 2016 - 10:28:18

Fichier

proper-cacti-TCS-FINAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva. Proper orientation of cacti. Theoretical Computer Science, Elsevier, 2016, 639, pp.14-25. 〈10.1016/j.tcs.2016.05.016〉. 〈hal-01338646〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

105