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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01338646
Contributor : Frederic Havet <>
Submitted on : Wednesday, June 29, 2016 - 12:49:26 AM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Document(s) archivé(s) le : Friday, September 30, 2016 - 10:28:18 AM

File

proper-cacti-TCS-FINAL.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

542

Files downloads

143