Arc-Weighted Acyclic Orientation of Graphs

Source abstract

Let $D$ be a digraph, and let $w: E(D) \to \{1,2,\ldots \}$ be a positive integer weight assignment on the arcs of $D$. An arc $e=(u,v)$ is called dominating if $w(e) > d_{(D,w)}^+(v)$, where $d_{(D,w)}^+(v)$ denotes the weighted out-degree of $v$. We say $(D,w)$ is acyclic if every non-empty sub-digraph $(D', w)$ has a dominating arc. For a graph $G$ and a mapping $f:V(G)\to\mathbb N$, we say $G$ is {arc-weighted $f$-degenerate} if there is an arc-weighted orientation $(D, w)$ of $G$ (i.e., an orientation $D$ of $G$ together with a positive integer weight assignment $w$) such that $(D,w)$ is acyclic and $d_{(D,w)}^+(v) \le f(v)$ for each vertex $v$. The arc-weighted degeneracy $d_{w}(G)$ of $G$ is the minimum $d$ such that $G$ is arc-weighted $d$-degenerate. Given an arc-weighted acyclic orientation $(D,w)$ of $G$ with $d_{(D,w)}^+(v) \le f(v)$, there is not only an easy algorithm that constructs an $(L,M)$-colouring of $G$ for any $(f+1)$-DP-cover $(L,M)$ of $G$, but also an easy winning strategy for the DP-$(f+1)$-painting game on $G$. Moreover, arc-weighted $f$-degeneracy implies $(f+1)$-Alon-Tarsi. As an arc-weighted acyclic orientation $(D,w)$ of $G$ with $w(e)=1$ for all $e$ is equivalent to a (non-weighted) acyclic orientation of $G$, $d_{w}(G)$ is bounded from above by the degeneracy $d(G)$ of $G$. We observe that the difference $d(G)-d_{w}(G)$ can be arbitrarily large. Thus, $d_{w}(G)+1$ can provide a better upper bound than $d(G)+1$ on its DP-paint number (and hence its DP-chromatic number, paint number and choice number), as well as its Alon-Tarsi number. Thomassen's proof of the 5-choosability of planar graphs can be easily adapted to prove that all planar graphs are arc-weighted $4$-degenerate, implying that planar graphs are DP-$5$-paintable as well as $5$-Alon-Tarsi. As an extension of the characterization of degree-choosable graphs, we prove that a connected graph $G$ is arc-weighted $(d_G-1)$-degenerate unless $G$ is a GDP-tree. In particular, $d_{w}(G) \le \Delta(G)-1$ unless $G$ is a complete graph or a cycle. Then we prove that 3-connected non-complete planar graphs are degree-truncated arc-weighted $14$-degenerate, implying that such graphs have degree-truncated DP-paint number at most $15$. The previously known upper bound for this parameter was $16$.