Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435192 | Theoretical Computer Science | 2016 | 12 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva,