Weak external bisections of regular graphs

DOI10.1007/S00373-024-02796-3MaRDI QIDQ6544518zbMATH OpenFDO

Authors Juan Yan, Ya-Hong Chen

Publication date 27 May 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00373-024-02796-3

zbMATH Keywords

2-factorexternal bisectionmaximum bisectionregular graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The article works on classical graph theory. It is devoted to the partial solution of the graph bisection problem. A bipartition of the graph $G$ is a bipartition of the set of vertices $- V(G)$, with $V(G)=V_1\cup V_2$ and $V_1\cap V_2=\emptyset$. If a bipartition satisfies $||V_1|-|V_2||\leq 1$, that is called a bisection of the graph. \textit{B. Bollobás} and \textit{A. D. Scott} [Random Struct. Algorithms 21, No. 3--4, 414--430 (2002; Zbl 1013.05059)] conjectured that each graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this article, the authors confirm this conjecture for some regular graphs. These results (obtained in the article) extend the results obtained by \textit{A. Ban} and \textit{N. Linial} [J. Graph Theory 83, No. 1, 5--18 (2016; Zbl 1346.05223)]. The authors also give an upper bound of the maximum bisection of graphs.

Recommendations

• On judicious bisections of graphs
• Bisections of graphs
• Balanced judicious bipartitions of graphs
• Balanced judicious partitions of (k,k-1)-biregular graphs
• Balanced judicious partitions of graphs with \(\Delta(G)-\delta(G))\leqslant 2\)

Cites work

• Bisections of graphs
• Graphic Sequences Have Realizations Containing Bisections of Large Degree
• Internal partitions of regular graphs
• Max-bisections of \(H\)-free graphs
• On problems about judicious bipartitions of graphs
• Problems and results on judicious partitions

This page was built for publication: Weak external bisections of regular graphs

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