Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs

DOI10.1016/J.AMC.2023.128126arXiv2204.08161OpenAlexW4378699810MaRDI QIDQ6108003

Xiangwen Li, Fangyu Tian, Lin Niu

Publication date: 29 June 2023

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: A {em $(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 {em $(d, h)$-decomposable} if $G$ has a $(d,h)$-decomposition. Let $G$ be a graph embeddable in a surface of nonnegative characteristic. In this paper, we prove the following results. (1) If $G$ has no chord $5$-cycles or no chord $6$-cycles or no chord $7$-cycles and no adjacent $4$-cycles, then $G$ is $(3,1)$-decomposable, which generalizes the results of Chen, Zhu and Wang [Comput. Math. Appl, 56 (2008) 2073--2078] and the results of Zhang [Comment. Math. Univ. Carolin, 54(3) (2013) 339--344]. (2) If $G$ has no $i$-cycles nor $j$-cycles for any subset ${i,j}subseteq {3,4,6}$ is $(2,1)$-decomposable, which generalizes the results of Dong and Xu [Discrete Math. Alg. and Appl., 1(2) (2009), 291--297].

Full work available at URL: https://arxiv.org/abs/2204.08161

zbMATH Keywords

decompositioncoloringlist coloringDP-coloringAlon-Tarsi number

Mathematics Subject Classification ID

Graph theory (05Cxx) Algebraic combinatorics (05Exx) Enumerative combinatorics (05Axx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• A note on list improper coloring of plane graphs
• Covering planar graphs with forests, one having bounded maximum degree
• Colorings and orientations of graphs
• The game coloring number of pseudo partial \(k\)-trees
• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• Improper choosability of graphs of nonnegative characteristic
• Decomposition of planar graphs with forbidden configurations
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• ON (3, 1)*-CHOOSABILITY OF TOROIDAL GRAPHS
• Game chromatic number of outerplanar graphs
• A note on list improper coloring planar graphs
• Decomposing planar graphs into graphs with degree restrictions

Related Items (1)

Decomposition of toroidal graphs without some subgraphs

This page was built for publication: Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs