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  class="mathmlsrc">itle="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516301438&_mathId=si1.gif&_user=111111111&_pii=S0304397516301438&_rdoc=1&_issn=03043975&md5=45b7feb11ca820da0d3921a72cd309e4">class="imgLazyJSB inlineImage" height="17" width="37" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397516301438-si1.gif">class="mathContainer hidden">class="mathCode">mi>χmi>→(<mi>Gmi>) 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.