Partitions of multigraphs without \(C_4\)
type: Item
instance of: scholarly article
title: Partitions of multigraphs without \(C_4\)
zbMATH Open document ID: 1483.05132
author: Jialei Song
author: Baogang Xu
published in: Graphs and Combinatorics
publication date: 2021-11-30T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 7435710
zbMATH Keywords: partition
zbMATH Keywords: degree constraints
zbMATH Keywords: subgraphs
reviewed by: Stephan Wagner
MaRDI profile type: Publication
full work available at URL: s00373-021-02335-4
OpenAlex ID: W3168636084
cites work: Decomposing Weighted Graphs
cites work: Efficient algorithms for decomposing graphs under degree constraints
cites work: Decomposing graphs with girth at least five under degree constraints
cites work: Q4820779
cites work: Partition of graphs with condition on the connectivity and minimum degree
cites work: On partitions of \(K_{2, 3}\)-free graphs under degree constraints
cites work: On decomposition of triangle-free graphs under degree constraints
cites work: On partitions of graphs under degree constraints
cites work: On a conjecture of Schweser and Stiebitz
cites work: Decomposing C4‐free graphs under degree constraints
cites work: Q4715286
cites work: Partitions of multigraphs under minimum degree constraints
cites work: Partitions of graphs and multigraphs under degree constraints
cites work: Graph decomposition with constraints on the connectivity and minimum degree
cites work: A note on partitions of graphs under degree constraints
DOI: 10.1007/S00373-021-02335-4
Recommended article: Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
Recommended article: On multigraphs with a given partition
Recommended article: Counting \(4 \times 4\) matrix partitions of graphs
Recommended article: On the choice number of complete multipartite graphs with part size four
Recommended article: Partitions of graphs and multigraphs under degree constraints
Recommended article: Vertex partitions of \(K_{4,4}\)-minor free graphs
Recommended article: Q2948814
Recommended article: Partitioning digraphs with outdegree at least 4
Recommended article: Q5747398
Recommended article: Q3758879
description: scientific article; zbMATH DE number 7435710