Partitions of multigraphs without \(C_4\) (Q2053675)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitions of multigraphs without \(C_4\) |
scientific article |
Statements
Partitions of multigraphs without \(C_4\) (English)
0 references
30 November 2021
0 references
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.
0 references
partition
0 references
degree constraints
0 references
subgraphs
0 references