Proper orientation of cacti

Description

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.

Abstract

International audience

Additional details