5 papers
NP-hardness of additive approximation for generalized Turán problems
Yihan Chen, Jialin He, Xihe Li +2
For a fixed graph and a fixed nonempty family of graphs, let denote the maximum number of copies of in an …
The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs
Yihan Chen, Tianying Xie
For graphs and , a spanning subgraph of is weakly -saturated in if the edges in can be added one at a time, each addition creating a new…
Saturation numbers for -uniform Berge-
Yihan Chen, Jialin He, Tianying Xie
The saturation number is the minimum number of hyperedges in an -uniform -saturated hypergraph on vertices. We determine this para…
On the -clique cover number of graphs
Yihan Chen, Jialin He, Tianying Xie
In 1966, Erdős, Goodman, and Pósa proved that cliques are sufficient to cover all edges in any -vertex graph, with tightness achieved by the balanced com…
Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree
Yihan Chen, Jialin He, Allan Lo +3
In 1975 Bollobás, Erdős, and Szemerédi asked what minimum degree guarantees an octahedral subgraph in any tripartite graph with vertices in each vertex class. We s…