2024/12/30 by Deng, Chenglong, Xuding Zhu, Zhu, Xuding
Engineering · Computer Science · #graph theory and CDMA systems #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2412.20811
An AT-orientation of a graph G is an orientation D of G such that the number of even Eulerian sub-digraphs and the number of odd Eulerian sub-digraphs of D are distinct. Given a mapping f: V(G) → ℕ, we say G is f-AT if G has an AT-orientation D with < f(v) for each vertex v. For a positive integer k, we say G is k-truncated degree-AT if G is f-AT for the mapping f defined as f(v) = min #k, dG(v)# . This paper proves that 2-connected outerplanar graphs other than odd cycles are 5-truncated degree-AT, and 2-connected bipartite outerplanar graphs are 4-truncated degree-AT. As a consequence, 2-connected outerplanar graphs other than odd cycles are 5-truncated degree paintable, and 2-connected bipartite outerplanar graphs are 4-truncated degree paintable. This improves the result of Hutchinson in [On list-coloring outerplanar graphs], where it was proved that maximal 2-connected outerplanar graphs other than are 5-truncated degree-choosable, and 2-connected bipartite outerplanar graphs are 4-truncated degree-choosable.