I am Yuhang Bai, a PhD candidate at Northwestern Polytechnical University (NWPU).
I am interested in Graph Theory and Theoretical Computer Science, particularly Approximation algorithms and Random Graph Theory.
Email:yuhang.bai66@gmail.com
[4] Yuhang Bai, Gyula O.H. Katona, Zixuan Yang. Most probably trangle-free graphs. arXiv preprint arXiv:2602.22782.
[3] Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink. Approximating maximum properly colored forests via degree bounded independent sets. arXiv preprint arXiv:2511.18263.
[2] Yichen Wang, Zixuan Yang, Xiamiao Zhao, Yuhang Bai, Junpeng Zhou. The Turán number of Berge matchings. arXiv preprint arXiv:2510.05422.
[1] Yuhang Bai, Kristóf Bérczi, Gergely Csáji, Tamás Schwarcz. Approximating maximum-size properly colored forests. arXiv preprint arXiv:2402.00834.
[9] Xiamiao Zhao, Zixuan Yang, Yichen Wang, Yuhang Bai, Junpeng Zhou. On Turán-type problems for Berge matchings. Submitted.
[8] Yuhang Bai, Gyula O.H. Katona, Zixuan Yang. Most probably trangle-free graphs. Submitted.
[7] Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink. Approximating maximum properly colored forests via degree bounded independent sets. Submitted.
[6] Yichen Wang, Zixuan Yang, Xiamiao Zhao, Yuhang Bai, Junpeng Zhou. The Turán number of Berge matchings. Submitted.
[5] Yuhang Bai, Shenggui Zhang. Properly colored thresholds. Submitted.
We extend both the threshold result of Frankston–Kahn–Narayanan–Park and its strengthening by Spiro to properly colored settings. In addition, we establish threshold results for some properly colored structures in randomly colored randomly perturbed graphs.
[4] Yuhang Bai, Shenggui Zhang, Yandong Bai, Jianhua Tu. The parameterized complexity of properly colored spanning trees problem. Submitted.
A weakly properly colored spanning tree $T$ with fixed root $r$ is a spanning tree in which every path in $T$, from $r$ to any leaf, is a properly colored path. We demonstrate that it is NP-complete to determine whether a planar graph contains a properly colored spanning tree, even for planar graphs with maximum degree four using only two colors. We also investigate the generalized properly colored spanning trees problem, where given a graph that every edge is assigned a set of colors, determine whether the graph contains a properly colored spanning tree, in which no two adjacent edges share a color. Surprisingly, this problem is polynomial-time solvable for trees but NP-hard for partial $2$-trees with each edge assigned at most two colors. Additionally, we prove that it is W[1]-hard to decide whether an edge-colored graph contains a weakly properly colored spanning tree when parameterized by the treewidth. On the positive side, we show that these problems are fixed-parameter tractable when parameterized by combining the treewidth and the number of colors.
[3] Yuhang Bai, Kristóf Bérczi, Gergely Csáji, Tamás Schwarcz. Approximating maximum-size properly colored forests. European Journal of Combinatorics, 132 (2026), 104269.
[2] Yanni Dong, Hajo Broersma, Yuhang Bai, Shenggui Zhang. The complexity of spanning tree problems involving graphical indices. Discrete Applied Mathematics, 347, 143-154.
[1] Yuhang Bai, Zhiwei Guo, Shenggui Zhang, Yandong Bai. Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs. Journal of Combinatorial Optimization, 45 (2), 73.
[1] Yuhang Bai, Kristóf Bérczi, Gergely Csáji, Tamás Schwarcz. Approximating maximum-size properly colored forests. In 32nd Annual European Symposium on Algorithms (ESA 2024), 308, 14:1-14:18.