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.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...