A sufficient condition for nonnegative characteristic graphs to be (2, 1)-decomposable

School of Mathematics and Statistics, Weifang University, Weifang 261061, P.R. China

^* Corresponding author: 906024652@qq.com

Received: 22 June 2023
Accepted: 26 March 2025

Abstract

A (d, h)-decomposition of a graph G is an order pair (D, H) such that H is a subgraph of G where H has the maximum degree at most h and D is an acyclic orientation of G − E(H) of maximum out-degree at most d. A graph G is (d, h)-decomposable if G has a (d, h)-decomposition. Let G be a graph embeddable in a surface of nonnegative characteristic. It is known that if G is (d, h)-decomposable, then G is h-defective (d + 1)-choosable. In this paper, we investigate the (d, h)-decomposable graphs and prove the following results. Every graph G is (2, 1)-decomposable if one of the following holds: (1) G has no intersecting i-cycles for all i = 3, 4, 5; (2) G has no 4-cycles nor intersecting 3-cycles. These results improve the results of Zhang who proved that every such graph is 1-defective 3-choosable. We also show that these results are sharp.