Proper orientation of cacti - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

Proper orientation of cacti

Résumé

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

Dates et versions

hal-01247014 , version 1 (20-12-2015)

Identifiants

  • HAL Id : hal-01247014 , version 1

Citer

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⟩
220 Consultations
296 Téléchargements

Partager

Gmail Facebook X LinkedIn More