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.
https://hal.inria.fr/hal-01247014
Contributeur : Frederic Havet
<>
Soumis le : dimanche 20 décembre 2015 - 23:22:53
Dernière modification le : mercredi 31 janvier 2018 - 10:24:05
Document(s) archivé(s) le : samedi 29 avril 2017 - 22:58:28
