Proper orientation number of triangle-free bridgeless outerplanar graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Proper orientation number of triangle-free bridgeless outerplanar graphs

Authors:	Jiangdong Ai Stefanie Gerke Gregory Gutin Yongtang Shi Zhenyu Taoqiu

Affiliation:	1. Department of Computer Science, Royal Holloway, University of London, Egham, UK;2. Department of Mathematics, Royal Holloway, University of London, Egham, UK;3. Center for Combinatorics and LPMC, Nankai University, Tianjin, China

Abstract:	An orientation of $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 neighboring vertices have different in-degrees. The proper orientation number of a graph $G$ , denoted by $\vec{χ} (G)$ , is the minimum maximum in-degree of a proper orientation of $G$ . Araujo et al asked whether there is a constant $c$ such that $◂≤▸ \vec{χ} (G) \leq c$ for every outerplanar graph $G$ and showed that $◂≤▸ \vec{χ} (G) \leq 7$ for every cactus $G$ . We prove that $◂≤▸ \vec{χ} (G) \leq 3$ if $G$ is a triangle-free 2-connected outerplanar graph and $◂≤▸ \vec{χ} (G) \leq 4$ if $G$ is a triangle-free bridgeless outerplanar graph.

Keywords:	outerplanar graph proper orientation proper orientation number