Article ID Journal Published Year Pages File Type
435192 Theoretical Computer Science 2016 12 Pages PDF
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
, , , ,