Gexin Yu

Research Interests

Graph theory and combinatorics

Research Papers:

• On the (1^2, 2^4)-packing edge-coloring of subcubic graphs (with Xujun Liu), arXiv: 2402.18353
• A new connectivity bound for a tournament to be highly linked (with Bin Chen, Xinmin Hou, and Xinyu Zhou), arXiv:2311.04068
• Cliques in Squares of Graphs with Maximum Average Degree less than 4 (with Dan Cranston), arXiv:2305.11763
• Toughness and the existence of k-factors in hypergraphs , (with Yuping Gao and Songling Shan), arXiv:2304.14172 .
• On the irregularity of uniform hypergraphs (with Hongying Liu and Bo Zhou), Linear Algebra Appl. 678 (2023), 107-124.
• Strong edge-coloring of 2-degenerate graphs (with Rachel Yu) Discrete Appl. Math. 336 (2023), 11–14.
• 1-planar graphs are odd 13-colorable, (with Runrun Liu and Weifan Wang), Discrete Math. 346 (2023), no. 8, Paper No. 113423, 7 pp.
• Optimal connectivity for fat-triangle linkages (with Runrun Liu and Martin Rolek) Discrete Math. 346 (2023), no. 5, Paper No. 113319, 5 pp.
• Spanning tree packing and 2-essential edge-connectivity. (with Xiaofeng Gu and Runrun Liu), Discrete Math. 346 (2023), no. 1, Paper No. 113132.
• Enhancing the Erdos-Lovasz Tihany Conjecture for line graphs of multigraphs (with Yue Wang), Journal of Graph Theory, (2022), 1-8
• Note on injective edge-coloring of graphs. (with Zhengke Miao and Yimin Song), Discrete Appl. Math. 310 (2022), 65-74.
• Open locating-dominating sets in circulant graphs, (with Robin Givens and Rex Kincaid), Discussiones Mathematicae Graph Theory 42(1) (2022) 47-62.
• Enhancing the Erdos-Lovasz Tihany Conjecture for graphs with independence number two (with Yue Wang), Discrete Math. 345 (2022), no. 4, Paper No. 112781, 5 pp.
• Planar graphs without $4$-cycles and intersecting triangles are $(1,1,0)$-colorable (with Runrun Liu and Xiangwen Li), Discrete Appl. Math. 304 (2021), 236247.
• Sufficient conditions for 2-dimensional global rigidity, (with W. Meng, M. Rolek, Y. Wang), SIAM J. Discrete Math. 35 (2021), no. 4, 2520-2534.
• An improved linear connectivity bound for tournaments to be highly linked. (with W. Meng, M. Rolek, Y. Wang) European J. Combin. 98 (2021), Paper No. 103390, 6 pp.
• Connectivity for kite-linked graphs. (with R. Liu, M. Rolek, C. Stephens, and Dong Ye) SIAM J. Discrete Math. 35 (2021), no. 1, 431446.
• Disjoint chorded cycles in graphs with high ore- degree. (with Alexandr Kostochka and Derrek Yager), Discrete mathematics and applications, 259304, Springer Optim. Appl., 165, Springer, Cham, 2020.
• The strong edge-coloring for graphs with small edge weight. (with Lily Chen, Mingfang Huang, and Xiangqian Zhou), Discrete Math. 343 (2020), no. 4, 111779, 11 pp.
• Planar graphs without $C_5$ and $K_4^-$ and adjacent $4$-cycles are $(2,0,0)$-colorable (with Xiangwen Li and Yuxue Yin), Discrete Math. 343 (2020), no. 2, 111661, 12 pp.
• Packing (1,1,2,2)-coloring of some subcubic graphs(with R. Liu, X. Liu, and M. Rolek), Discrete Appl. Math. 283 (2020), 626630.
• Planar graphs without short even cycles are near-bipartite (with R. Liu), Discrete Appl. Math. 284 (2020), 626630.
• DP-4-colorability of planar graphs without given two adjacent cycles (with Runrun Liu, Xiangwen Li, Kittikorn Nakprasit, Pongpat Sittitrai), Discrete Appl. Math. 277 (2020), 245251.
• Planar graphs without 7-cycles and butterflies are DP-4-colorable (with Seog-Jin Kim and Runrun Liu), Discrete Math. 343 (2020), no. 8, 111714, 9 pp.
• Deng, Kecai; Yu, Gexin; Zhou, Xiangqian, Recent progress on strong edge-coloring of graphs. Discrete Math. Algorithms Appl. 11 (2019), no. 5, 1950062, 21 pp.
• DP-4-colorability of two classes of planar graphs (with Lily Chen, Runrun Liu, Ren Zhao and Xiangqian Zhou), Discrete Math. 342 (2019), no. 11, 2984-2993.
• DP-3-coloring of planar graphs without $\{4,9\}$-cycles and two cycles from $\{6,7,8\}$ (with Runrun Liu, Sarah Loeb, Martin Rolek, Yuxue Yin), Graphs and Combinatorics, 35 (2019), Issue 3, pp 695-705.
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable (with Yuxue Yin), Discrete Math., 342 (2019), no. 8, 2333-2341.
• DP-3-coloring of planar graphs (with Runrun Liu, Sarah Loeb and Yuxue Yin), Discrete Math. 342 (2019), no. 1, 178-189.
• Minimum degree condition for a graph to be knitted (with R. Liu and M. Rolek), Discrete Math. 342 (2019), no. 11, 32253228.
• Planar graphs with girth at least $5$ are $(3,4)$-colorable (with Ilkyoo Choi and Xia Zhang), Discrete Math. 342 (2019), no. 12.
• Strong edge-coloring of planar graphs with large girth (With Lily Chen, Kecai Deng and Xiangqian Zhou), Discrete Math. 342 (2019), no. 2, 339-343.
• Planar graphs without 4-cycles and close triangles are (2,0,0)-colorable, (with Heather Hoskins^*, Runrun Liu^**, Jennifer Vandenbussche), J. of Comb. Optim., 36 (2018) 346-364.
• A relaxation of the strong Bordeaux Conjecture (with Ziwen Huang^** and Xiangwen Li), J. of Graph Theory, 88 (2018) 237-254. DOI: 10.1002/jgt.22208. (18 pages)
• Strong chromatic index of graphs with maximum degree four (with Mingfang Huang and Mike Santana), Electronic J. of Combinatorics, 25 (3) (2018), P3.31.
• Strong choice number of subcubic graphs (with Tianjiao Dai, Guanghui Wang, Donglei Yang), Discrete Math., 341 (2018), Issue 12, 3434--3440.
• On strong edge-coloring of graphs with maximum degree four (with Jian-Bo Lv^** and Xiangwen Li), Discrete Applied Math., 235 (2018), 142--153.
• An integer linear program for mixed-weight open locating-dominating sets, (with Robin Givens, Rex Kincaid, and Weizheng Mao), 52st Annual Conference on Information Systems and Sciences (CISS2018), March 21-22, 2018, Princeton University.
• Covering 2-connected 3-regular graphs with disjoint paths, Journal of Graph Theory, 88 (2018), 385-401.
• The strong chromatic index of (3,\Delta)-bipartite graphs (with Minfang Huang and Xiangqian Zhou), Discrete Math., 340 (2017), no. 5, 1143--1149.
• Maximum average degree and relaxed coloring (with Michael Kopreski^*). Discrete Math. 340 (2017), no. 10, 2528--2530.
• Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1,1,0)-colorable, (with Ying Bai^** and Xiangwen Li), J. Comb. Optimization, 33 (2017), 1354--1364.
• A note on chromatic number and induced odd cycles (with Baogang Xu and Xiaoya Zha), Electronic J. of Combinatorics, 24 (4) (2017), P4.32. (8 pages)
• Extremal permutations in routing cycles (with Junhua He, Louis A. Valentin^* and Xiaoyan Yin), Electronic Journal of Combinatorics, Volume 23, Issue 3 (2016), Paper P3.47.
• An Upper Bound on the Number of Circular Transpositions to Sort a Permutation (with Anke van Zuylen, James Bieron, Frans Schalekamp) Inform. Proc. Letter, 116 (2016) 718-722.
• Strong chromatic index of subcubc planar multigraphs (with A.V. Kostochka, X. Li, W. Ruksasakchai, M. Santana, T. Wang), European J. Combinatorics, 51 (2016) 380-397.
• Planar graphs without 5-cycles and intersecting triangles are (1,1,0)-colorable, (with Runrun Liu and Xiangwen Li), Discrete Math., 339 (2016) 992-1003.
• Strong edge-colorings for k-degenerate graphs Graphs and Comb., 31 (2015) 1815-1818.
• A relaxation of the Bordeaux Conjecture (with Runrun Liu and Xiangwen Li) European J. Combinatorics, 49 (2015) 240-249.
• Optimal open-locating-dominating sets in infinite triangular grids (with Rex Kincaid, Allison Oldham), Discrete Appliced Math., 193 (2015) 139-144.

Papers before 2014

Graph linkage

• Connectivity for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture (with K. Kawarabayashi) to appear in J. of Comb. Theory Ser. B
• Linkage for the diamond and the path with four vertices (with Mark Ellingham and Mike Plummer) accepted by Journal of Graph Theory
• Implications among linkage properties in graphs (with Q. Liu and D. West), J. Graph Theory 60 (2009), no. 4, 327--337.
• On Ore-type degree condition for a graph to be $H$-linked (with A. Kostochka), J. Graph Theory, 58 (2008) 14-26.
• Minimum degree conditions for $H$-linked graphs (with A. Kostochka), Disc. Appl. Math 156 (2008) 1542-1548.
• A lower bound for minimum degree in $H$-linked graphs (with R. Gould, A. Kostochka), SIAM J. on Discrete Math (SIDMA) 20 (2006), 829-840.
• On Degree Conditions for a Graph to be $k$-linked (with K. Kawarabayashi, A. Kostochka), Combinatorics, Probability and Computing 15 (2006), 685--694.
• An extremal problem for $H$-linked graphs (with A. Kostochka), J. Graph Theory 50 (2005), 321-339.

Graph packing

• Graphs containing every 2-factor.pdf (with A. Kostochka) to appear in Graphs and Combinatorics
• Ore-conditions implying 2-factors consisting of short cycles (with A. Kostochka), Discrete Mathematics 309 (2009) 4762-4771.
• Extremal graph packing problems: Ore-type versus Dirac-type (with H. Kierstead and A. Kostochka), London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009.
• Packing of graphs with small product of sizes (with A. Kostochka), J. Combin. Theory Ser. B 98 (2008), no. 6, 1411--1415.
• On a graph packing conjecture of Bollob\'as, Eldridge and Catlin (with H. Kaul, A. Kostochka), Combinatorica 28 (2008), no. 4, 469--485.
• An Ore-type analogue of the Sauer-Spencer Theorem (with A. Kostochka), Graphs and Combinatorics 23 (2007) no 4, 419-424.
• Ore-type graph packing problems (with A. Kostochka), Combinatorics, Probability and Computing 16 (2007), 167-169.

Graph coloring

• Planar graphs without 4- or 5-cycles are $(3,0,0)$-colorable (with O. Hill, J. Xu, D. Smith, Y. Wang), submitted.
• A note on strong edge-coloring of 2-degenerate graphs (with R. Luo)
• A relaxation of Steinberg's Conjecture (with Owen Hill) to appear in SIAM J. of Disc. Math.
• Linear colorings of subcubic graphs (with Chun-Hung Liu) submitted.
• Linear Choosability of Sparse Graphs (with Dan Cranston) Discrete Math., 311 (2011), 1910--1917.
• Injective colorings of graphs with low average degree (with Dan Cranston and Seog-Jin Kim) Algorithmica 60 (2011) 553-568.
• Equitable defective coloring of sparse planar graphs (with Lee Williams and Jennifer Vandenbussche) Disc. Math., 312 (2012), no. 5, 957--962.
• Equitable coloring sparse planar graphs (with Rong Luo, Jean-Sebastien Sereni, and Chris Stephen) SIAM J. Discrete Math 24 (2010) 1572-1583.
• Injective colorings of sparse graphs (with Dan Cranston and Seog-Jin Kim) Discrete Math. 310 (2010) 2965-2973.
• First-Fit chromatic numbers of planar and random graphs (with J. Balogh, S. Hartke, and Q. Liu), SIAM J. on Discrete Mathematics 22 (2008), 887-900.
• An inequality for the group chromatic number of a graph (with Hong-Jian Lai and Xiangwen Li), Discrete Mathematics, 307 (2007) 3076-3080.

Group connectivity

• An Extremal problem on group connectivity of graphs (with R. Luo, R. Xu) European J. Combinaotorics, 33 (2012) 6, 1078--1085
• Ore-condition and $Z_3$-connectivity (with Rong Luo, Rui Xu and Jianhua Yin), European J. of Combinatorics 29 (2008) 1587-1595.
• Nowhere-zero $Z_3$-flows through $Z_3$-connectivity (with M. DeVos, R. Xu), Discrete Mathematics 306 (2006), 26-30.

Graph decompositions

• M-degrees and $C_4$-free planar graphs (with O. Borodin, A Kostochka, and N. Sheikh), J. Graph Theory 60 (2009), no. 1, 80--85.
• Planar graphs with girth $9$ can be edge-partitioned into a forest and a matching (with O. Borodin, A Kostochka, and N. Sheikh), European J. of Combinatorics, 29 (2008) 1235-1248.

Other topics (vertex identifying code, page number, routing numbers, et al)

• Perfect partition of some regular partite graphs, (with Jeff Soosiah and C.-K. Li), submitted.
• Toward Efficient Channel Hopping for Communication Rendezvous in Dynamic Spectrum Access Networks (Y. Zhang, G. Yu, Q. Li, H. Wang, G. Zhu, and B. Wang), submitted to IEEE/ACM Transactions on Networking.
• New bounds on the minimum density of a vertex identifying code for the infinite hexagonal grid (with Ari Cukierman)
• Permutations as product of parallel transpositions (with Chase Albert, Chi-Kwong Li, and Gil Strang)SIAM J. Disc. Math., 25 (2012), 1412--1417.
• ETCH: EfficienT Channel Hopping for Communication Rendezvous in Dynamic Spectrum Access Networks. (with Yifan Zhang, Qun Li, and Baosheng Wang). IEEE Infocom, Shanghai, China, April 10-15, 2011.
• A new bound on the density of vertex identifying codes for the infintie hexagonal grid (with Dan Cranston) Electronic Journal of Combinatorics 16 (2009) no 1, research paper 113. (16 pages)
• On the pagenumebr of k-trees (with J. Vandenbussche, D.B. West), SIAM J. on Discrete Mathematics 23 (2009) 1455-1464.
• Hamiltonian connectedness in 3-connected line graphs. (with H.-J. Lai, Y. Shao and M. Zhan), Discrete Appl. Math. 157 (2009), no. 5, 982--990.
• On the minimum 2-wide wide diameter of Cylces with Chords (with B. Liu and X. Hou) Operation Research Transactions (Chinese) 13 (2009) 1-5.
• On extremal matrices of second large exponent by boolean rank (with B. Liu and L. You), Linear Algebra and Application 422 (2007) 186-197.
• On maximal $(k,b)$-free sets of integers and its spectrum (with B. Liu and L. You), Austra.. J. Combin. 23 (2001), 211--215.