Proper orientation number of triangle-free bridgeless outerplanar graphs. / Ai, Jiangdong; Gerke, Stefanie; Gutin, Gregory; Shi, Yongtang; Taoqiu, Zhenyu.

In: Journal of Graph Theory, 20.04.2020, p. 1-11.

Research output: Contribution to journalArticle

E-pub ahead of print

Documents

  • Accepted Manuscript

    Accepted author manuscript, 289 KB, PDF document

    Embargo ends: 20/04/21

Abstract

An orientation of a graph G is a digraph obtained from G by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation proper if neighbouring vertices have different in-degrees. The proper orientation number of a graph G, denoted by \chi(G), is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant c such that \chi(G)< c for every outerplanar graph $G$ and showed that \chi}(G) <= 7$ for every cactus G. We prove that \chi}(G) <=3 if G is a triangle-free 2-connected outerplanar graph and $\chi (G) <= 4$ if G is a triangle-free bridgeless outerplanar graph.
Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalJournal of Graph Theory
Early online date20 Apr 2020
DOIs
Publication statusE-pub ahead of print - 20 Apr 2020
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 37485670