Can I read On the Proper Orientation Number of Chordal Graphs on EtoBox?

On the Proper Orientation Number of Chordal Graphs by Araujo, Julio; Cezar, Alexandre; Lima, Carlos V. G. C.; Santos, Vinicius F. dos; Silva, Ana is a scholarly article available to read on EtoBox.

What is On the Proper Orientation Number of Chordal Graphs about?

An orientation $D$ of a graph $G=(V,E)$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each $v \in V(G)$, the indegree of $v$ in $D$, denoted by $d^-_D(v)$, is the number of arcs with head $v$ in $D$. An orientation $D$ of $G$ is proper if $d^-_D(u)\neq d^-_D(v)$, for all $uv\in E(G)$. An orientation with maximum indegree at most $k$ is called a $k$-orientation. The proper orientation number of $G$, denoted by $\overrightarrow{\chi}(G)$, is the minimum integer $k$ such that $G$ admits a proper $k$-orientation. We prove that determining whether $\overrightarrow{\chi}(G) \leq k$ is NP-complete for chordal graphs of bounded diameter, but can be solved in linear-time in the subclass of quasi-threshold graphs. When parameterizing by $k$, we argue that this problem is FPT for chordal graphs and argue that no polynomial kernel exists, unless $NP\subseteq coNP/\ poly$. We present a better kernel to the subclass of split graphs and a linear kernel to the class of cobipartite graphs. Concerning bounds, we prove tight upper bounds for subclasses of block graphs. We also present new families of trees having proper o

Author

Araujo, Julio; Cezar, Alexandre; Lima, Carlos V. G. C.; Santos, Vinicius F. dos; Silva, Ana

Published

2020

Language

EN