4 papers
Sharp asymptotics for triangle independence and covering numbers
Zhen Liu, Qinghou Zeng
For a graph , let be the maximum size of an edge set containing at most one edge from every triangle, and let be the minimum size of an edge set meeting every…
Paths of even length with equal-degree endpoints
Kaizhe Chen, Zhen Liu, Qinghou Zeng
Addressing a question posed by Erdős and Hajnal, Chen and Ma proved that, for all , the complete bipartite graph is the unique graph on vertices with…
A complement of the Erdős-Hajnal problem on paths with equal-degree endpoints
Zhen Liu, Qinghou Zeng
Answering a question of Erdős and Hajnal, Chen and Ma proved that for all \(n\geq600\) every graph with \(2n + 1\) vertices and at least \(n^2 + n+1\) edges contains two vertices o…
Equating three degrees of graphs
Zhen Liu, Qinghou Zeng
In this paper, we prove that, for every graph with at least 5 vertices, one can delete at most 3 vertices such that the subgraph obtained has at least three vertices with the same…