5 papers
Joins and ear decompositions beyond graphic matroids
Yuhang Bai, Kristóf Bérczi, Chaitanya Nalam
For a matroid , a join is a set that meets every circuit in at most elements. Let denote the maximum size of a join. Motivated by Frank's m…
Above-Guarantee Algorithm for Properly Colored Trees
Yuhang Bai, Kristóf Bérczi
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct c…
Most probably trangle-free graphs
Yuhang Bai, Gyula O. H. Katona, Zixuan Yang
The celebrated Mantel's theorem states that any triangle-free graph on vertices contains at most edges. It is natural to ask how many triangle…
The Turán number of Berge matchings
Yichen Wang, Zixuan Yang, Xiamiao Zhao +2
Given a graph , an -uniform hypergraph is a {\em Berge-} if there is a bijection such that for each $e\in E(F)…
Approximating maximum properly colored forests via degree bounded independent sets
Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink
In the Maximum-size Properly Colored Forest problem, we are given an edge-colored undirected graph and the goal is to find a properly colored forest with as many edges as possible.…