Proper orientation of cacti

详细信息    查看全文

• 作者：Julio Araujo^a ; ^{julio@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Fré ; dé ; ric Havet^b ; ¹ ; ^{frederic.havet@cnrs.fr" class="auth_mail" title="E-mail the corresponding author} ; Claudia Linhares Sales^c ; ² ; ^{linhares@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Ana Silva^a ; ³ ; ^{anasilva@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Proper orientation ; Graph coloring ; Cactus graph ; Claw-free graph ; Planar graph ; Block graph
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：1 August 2016
• 年：2016
• 卷：639
• 期：Complete
• 页码：14-25
• 全文大小：501 K

文摘

An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number  $\overrightarrow{\chi }(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.