Partitions of multigraphs without C₄
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.
- Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
- On multigraphs with a given partition
- Counting 4 4 matrix partitions of graphs
- On the choice number of complete multipartite graphs with part size four
- Partitions of graphs and multigraphs under degree constraints
- Vertex partitions of \(K_{4,4}\)-minor free graphs
- On the multidecompositions of the complete multipartite graphs into the graph-pair of order 4
- Partitioning digraphs with outdegree at least 4
- Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs
- scientific article; zbMATH DE number 4008444
- A note on partitions of graphs under degree constraints
- Decomposing C₄-free graphs under degree constraints
- Decomposing graphs with girth at least five under degree constraints
- Decomposing weighted graphs
- Efficient algorithms for decomposing graphs under degree constraints
- Graph decomposition with constraints on the connectivity and minimum degree
- scientific article; zbMATH DE number 944226 (Why is no real title available?)
- scientific article; zbMATH DE number 2104729 (Why is no real title available?)
- On a conjecture of Schweser and Stiebitz
- On decomposition of triangle-free graphs under degree constraints
- On partitions of \(K_{2, 3}\)-free graphs under degree constraints
- On partitions of graphs under degree constraints
- Partition of graphs with condition on the connectivity and minimum degree
- Partitions of graphs and multigraphs under degree constraints
- Partitions of multigraphs under minimum degree constraints
- Partitions of multigraphs under minimum degree constraints
- Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
- Partitions of graphs and multigraphs under degree constraints
- \(C_{4p}\)-frame of complete multipartite multigraphs
- On a conjecture of Schweser and Stiebitz
- On connected partition with degree constraints
- Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
- Decomposing C₄-free graphs under degree constraints
- Distribution of vertices required a high-degree condition on partitions of graphs under degree constraints
This page was built for publication: Partitions of multigraphs without \(C_4\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053675)
