On connected partition with degree constraints

DOI10.1016/J.DISC.2021.112680MaRDI QIDQ2666577zbMATH OpenOpenAlexFDO

Authors Muhuo Liu, Baogang Xu

Publication date 23 November 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2021.112680

zbMATH Keywords

connected graphsdegreepartitionsubgraph

Mathematics Subject Classification ID

Vertex degrees (05C07) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(s\) and \(t\) be nonnegative integers, and let \(f(s,t)\) be the smallest positive integer such that every \(f(s,t)\)-connected graph \(G\) has a partition \(\{S,T\}\) of \(V(G)\) such that \(G[S]\) is \(s\)-connected and \(G[T]\) is \(t\)-connected. \textit{C. Thomassen} [Selected topics in graph theory, Vol. 3, 97--131 (1988; Zbl 0659.05062)] conjectured that \(f(s,t)=s+t+1\) for all positive integers \(s\) and \(t\). The best known bound for \(f(s,t)\) is \(f(s,t) \le 4s+4t-13\) if \(s\ge 3\) and \(t\ge 2\) due to \textit{P. Hajnal} [Combinatorica 3, 95--99 (1983; Zbl 0529.05030)]. The authors improve \(f(s,t)\) to \(\lceil \frac{19(s-1)}{6}+\rceil+\lceil \frac{19(t-1)}{6}+\rceil+1\) if \(\min\{s,t\} \ge 3\). They also improve the upper bound \(g(s,t)\) for some special classes of graphs, where \(g(s,t)\) is the smallest integer such that every graph \(G\) with minimum degree \(g(s,t)\) has a partition \(\{S,T\}\) of \(V(G)\) such that \(G[S]\) has minimum degree at least \(s\) and \(G[T]\) has minimum degree at least \(t\).

Recommendations

• On partitions of graphs under degree constraints
• Partitions of graphs with high minimum degree or connectivity.
• Partitions of graphs and multigraphs under degree constraints
• On partitions of \(K_{2, 3}\)-free graphs under degree constraints
• Bipartition of graph under degree constraints

Cites work

• 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 4077268 (Why is no real title available?)
• scientific article; zbMATH DE number 3627227 (Why is no real title available?)
• 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
• On the number of edges in a graph with no \((k + 1)\)-connected subgraphs
• 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 without \(C_4\)

Cited in

(8)

• Partitions of graphs with high minimum degree or connectivity.
• Partitions of multigraphs under minimum degree constraints
• On partitions of \(K_{2, 3}\)-free graphs under degree constraints
• Mixed partition functions and exponentially bounded edge-connection rank
• On partitions of graphs under degree constraints
• Bipartition of graph under degree constraints
• Partitioning a graph into highly connected subgraphs
• Graph partitions under average degree constraint

This page was built for publication: On connected partition with degree constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2666577)