Arc weighted acyclic orientations and variations of degeneracy of graphs

Abstract

This paper studies generalizations of the concept of acyclic orientations to arc-weighted orientations. These lead to four types of variations of strict degeneracy of graphs. Some of these variations are studied in the literature under different names and we put them in a same framework for comparison. Then we concentrate on one of these variations, which is new and is defined as follows: For a graph $G$ and a mapping $f\in {\mathbb{N}}^G$, we say $G$ is $S{T}^{(2)}$-$f$-degenerate if there is an arc-weighted orientation $(D,w)$ of $G$ such that $d_{(D,w)}^{+}(v)<f(v)$ for each vertex $v$, and every sub-digraph $D^{\prime }$ of $D$ contains an arc $e=(u,v)$ with $w(e)>d_{(D^{\prime },w)}^{+}(v)$. We prove that if $G$ is $S{T}^{(2)}$-$f$-degenerate, then $G$ is $f$-paintable, as well as $f$-AT. Then we use $S{T}^{(2)}$-degeneracy to study truncated degree choosability of graphs. A graph $G$ is called $k$-truncated degree-choosable (respectively $S{T}^{(2)}$-$k$-truncated degree degenerate) if $G$ is $f$-choosable (respectively, $S{T}^{(2)}$-$f$-degenerate), where $f(v)=\min \{k,d_G(v)\}$. Richter asked whether every 3-connected non-complete planar graph is $6$-truncated-degree-choosable. We answer this question in negative by constructing a 3-connected non-complete planar graph which is not $7$-truncated-degree-choosable. On the other hand, we prove that every 3-connected non-complete planar graph is $S{T}^{(2)}$-$16$-truncated-degree-degenerate, and hence $16$-truncated-degree-choosable. We further prove that for an arbitrary proper minor closed family $\mathcal{G}$ of graphs, let $s$ be the minimum integer such that $K_{s,t}\notin \mathcal{G}$ for some $t$, then there is a constant $k$ such that every $s$-connected non-complete graph $G\in \mathcal{G}$ is $S{T}^{(2)}$-$k$-truncated-degree-degenerate and hence $k$-truncated-degree-choosable.

24 pages, 1 figure