Partitions of multigraphs without \(C_4\)
Consider a multigraph \(G\) (with multiedges, but no loops), let \(\mu(u,v)\) be the number of edges between \(u\) and \(v\), and let \(\mu(u) = \max_v \mu(u,v)\) be the maximum number of edges going from \(u\) to another vertex \(v\). Let \(a\), \(b\) be two given functions from the set of vertices of \(G\) to the set \(\mathbb{N} \setminus \{0,1\} = \{2,3,\ldots\}\) that satisfy \(d_G(v) \geq a(v) + b(v) + 2\mu(v) - 3\) for all vertices \(v\). The main result of the paper states that, if \(G\) does not contain the \(4\)-cycle \(C_4\), then for any two such functions \(a\) and \(b\), the vertex set can be partitioned into two sets \(A\) and \(B\) such that \(d_{G[A]}(u) \geq a(u)\) for all \(u \in A\) and \(d_{G[B]}(v) \geq b(v)\) for all \(v \in B\). This generalizes a theorem of \textit{J. Ma} and \textit{T. Yang} [J. Graph Theory 90, No. 1, 13--23 (2019; Zbl 1414.05239)] on simple graphs.
scientific article; zbMATH DE number 7435710
scientific article