15 papers
On several judicious partitioning problems of graphs and hypergraphs
Siwei Lin, Qinghou Zeng
Judicious partition problems ask for vertex partitions of graphs or hypergraphs that optimize several quantities simultaneously. In this paper, we investigate judicious partitions…
Internal partitions of -regular and -regular graphs
Siwei Lin, Qinghou Zeng
An \emph{internal partition} of a graph is a partition of its vertex set into two nonempty parts such that every vertex has at least half of its neighbors in its own part. DeVos as…
The error term for judicious partitions of 3-uniform hypergraphs
Siwei Lin, Qinghou Zeng
Let be a fixed integer. Bollobás and Scott proved that every -uniform hypergraph with edges admits a partition of its vertex set into parts such that each part s…
Melnikov's Valency Variety Problem
Zhanping Yang, Qinghou Zeng
Let denote the number of distinct vertex degrees of a finite simple graph . Melnikov asked for a lower bound on the chromatic number in terms of and $w(G)…
Intersections of Directed Graphs
Zhanping Yang, Qinghou Zeng
Given two weighted directed graphs of order \(n\), we study how much their overlap can deviate from its random average under relabelling, and how concentrated the distribution of t…
Sharp Bisection Bounds for Digraphs
Zhaoyang Ma, Shufei Wu, Qinghou Zeng
Fix an integer . We prove that, for all sufficiently large , every digraph with arcs and minimum semidegree at least admits a bisection wit…
Large odd induced subgraphs via odd cuts
Qinghou Zeng
Gallai proved that every graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We show that if a graph admits a bipartition in which every vertex…
Max-Bisections of graphs without even cycles
Jianfeng Hou, Siwei Lin, Qinghou Zeng
For an integer , let be a graph with edges and without cycles of length . The pivotal Alon-Krivelevich-Sudakov Theorem on Max-Cuts states that has a biparti…
Graded discrepancy of graphs and hypergraphs
Yanling Chen, Shuping Huang, Qinghou Zeng
This paper studies the following question of Bollobás and Scott: Let be a graph with vertices and edges. What is the smallest such that there is a…
Counting triangles in graphs without vertex disjoint odd cycles
Jianfeng Hou, Caihong Yang, Qinghou Zeng
Given two graphs and , the maximum possible number of copies of in an -free graph on vertices is denoted by . Let denote…
MaxCut in graphs with sparse neighborhoods
Jinghua Deng, Jianfeng Hou, Siwei Lin +1
Let be a graph with edges and let denote the size of a largest cut of . The difference is called the surplus of $G…
Extremal graphs for the suspension of edge-critical graphs
Jianfeng Hou, Heng Li, Qinghou Zeng
The Turán number of a graph , , is the maximum number of edges in an -vertex graph that does not contain as a subgraph. For a vertex and a multi-set $…
Two stability theorems for -saturated hypergraphs
Jianfeng Hou, Heng Li, Caihong Yang +2
An -saturated -graph is a maximal -graph not containing any member of as a subgraph. Let be the collection of all -…
Perfect codes in quintic Cayley graphs on abelian groups
Yuefeng Yang, Xuanlong Ma, Qing Zeng
A subset of the vertex set of a graph is called a perfect code of if every vertex of is at distance no more than one to exactly one vertex in . In this paper, we…
A generalization of Stiebitz-type results on graph decomposition
Qinghou Zeng, Chunlei Zu
In this paper, we consider the decomposition of multigraphs under minimum degree constraints and give a unified generalization of several results by various researchers. Let be…