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
Journal of Theoretical Computer Science (TCS), Elsevier, 2016, 639, pp.14-25. <10.1016/j.tcs.2016.05.016>
Liste complète des métadonnées


https://hal.inria.fr/hal-01338646
Contributeur : Frederic Havet <>
Soumis le : mercredi 29 juin 2016 - 00:49:26
Dernière modification le : vendredi 1 juillet 2016 - 01:04:34
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. Journal of Theoretical Computer Science (TCS), Elsevier, 2016, 639, pp.14-25. <10.1016/j.tcs.2016.05.016>. <hal-01338646>

Partager

Métriques

Consultations de
la notice

268

Téléchargements du document

79