Proper orientation of cacti - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2016

Proper orientation of cacti

Résumé

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.
Fichier principal
Vignette du fichier
proper-cacti-TCS-FINAL.pdf (464.05 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01338646 , version 1 (29-06-2016)

Identifiants

Citer

Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva. Proper orientation of cacti. Theoretical Computer Science, 2016, 639, pp.14-25. ⟨10.1016/j.tcs.2016.05.016⟩. ⟨hal-01338646⟩
224 Consultations
184 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More