Decompositions of graphs with degree constraints relative to prescribed subgraphs

Peichao Wei; Muhuo Liu; Yang Wu; Zoran Stani\' c

paper

Decompositions of graphs with degree constraints relative to prescribed subgraphs

arXiv:2509.23078

Abstract

Given a finite simple undirected graph $G$ , let $T_{1} (G)$ denote the subset of vertices of $G$ such that every vertex of $T_{1} (G)$ belongs to at least one subgraph isomorphic to a graph obtained by connecting a single vertex to two vertices of $K_{4} - e$ . Define $T_{0} (G) = V (G) ∖ T_{1} (G)$ , and let $a, b : V (G) ⟶ Z_{\geq 0}$ be arbitrary functions. In this paper, we prove that if $d_{G} (u) \geq a (u) + b (u) + h (u)$ , where $h (u) \in {0, 1}$ for $u \in T_{h} (G)$ , then there exists a partition $(S, T)$ of $V (G)$ such that $d_{S} (u) \geq a (u)$ for every $u \in S$ and $d_{T} (u) \geq b (u)$ for every $u \in T$ . This result extends the theorem of Stiebitz~[\textit{J. Graph Theory}, 23 (1996), 321--324]. Moreover, we establish an analogous result in the case where $T_{1} (G)$ consists of vertices belonging to at least one $K_{2, 3}$ , thereby extending the findings of Hou et al.~[\textit{Discrete Math.}, 341 (2018), 3288--3295].