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 is proper if two adjacent vertices have different indegrees. We prove that every cactus admits a proper orientation with maximum indegree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum indegree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum indegree at most 6 and that this bound can also be attained.
Type de document :
Rapport
[Research Report] RR-8833, INRIA Sophia Antipolis - Méditerranée. 2015, pp.17
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01247014
Contributeur : Frederic Havet <>
Soumis le : dimanche 20 décembre 2015 - 23:22:53
Dernière modification le : vendredi 16 septembre 2016 - 15:13:51
Document(s) archivé(s) le : samedi 29 avril 2017 - 22:58:28

Fichier

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

Identifiants

  • HAL Id : hal-01247014, version 1

Collections

Citation

Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva. Proper orientation of cacti. [Research Report] RR-8833, INRIA Sophia Antipolis - Méditerranée. 2015, pp.17. 〈hal-01247014〉

Partager

Métriques

Consultations de
la notice

462

Téléchargements du document

155