6 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 mi…
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…
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.…
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 .…
Approximating maximum-size properly colored forests
Yuhang Bai, Kristóf Bérczi, Gergely Csáji +1
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in whic…