Gexin Yu

Research Interests:

Graph theory and combinatorics, and its applications.

Research Papers:

Graph Linkage

• Fat-triangle linkage and kite-linked graphs (with R. Liu and M. Rolek), submitted.
• Minimum degree condition for a graph to be knitted (with R. Liu and M. Rolek), Discrete Math.
• Every t-chromatic graph contains a 8-connected minor for t at least 15 (with R. Liu and M. Rolek), submitted.
• Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture (with K. Kawarabayashi) J. Comb. Theory Ser. B, 103 (2013), no. 3, 320--326.
• On Ore-type degree condition for a graph to be H-linked (with A. Kostochka), J. Graph Theory, 58 (2008) 14-26.
• Linkage for the diamond and the path with four vertices (with M. Ellingham and M. Plummer) J. of Graph Theory, DOI: 10.1002/jgt.20612
• Implications among linkage properties in graphs (with Q. Liu and D. West), J. Graph Theory 60 (2009), no. 4, 327--337.
• 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.

Path cover number

• Covering 2-connected 3-regular graphs with disjoint paths, Journal of Graph Theory, 88 (2018), 385-401.

Graph decompositions

• Planar graphs without short even cycles are near-bipartite (with R. Liu), submitted.
• 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.

Graph Packing

• Packing (1,1,2,2)-coloring of some subcubic graphs(with R. Liu, X. Liu, and M. Rolek),
• Graphs containing every 2-factor.pdf (with A. Kostochka) 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.
• Graphs containing every 2-factor (with A. Kostochka) Graphs and Combinatorics, DOI 10.1007/s00373-011-1066-6.
• 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.

DP-coloring of planar graphs

• Planar graphs without 7-cycles and butterflies are DP-4-colorable (with Seog-Jin Kim and Runrun Liu), submitted.
• DP-3-coloring of planar graphs (with Runrun Liu, Sarah Loeb and Yuxue Yin), Discrete Math.
• DP-4-colorability of two classes of planar graphs (with Lily Chen, Runrun Liu, Ren Zhao and Xiangqian Zhou), Discrete Math.
• 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.
• DP-4-colorability of planar graphs without given two adjacent cycles (with Runrun Liu, Xiangwen Li, Kittikorn Nakprasit, Pongpat Sittitrai), Discrete Applied Math.
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable (with Yuxue Yin), Discrete Math.

  Strong Edge-coloring

• Strong chromatic index of graphs with maximum degree four (with Mingfang Huang and Mike Santana), Electronic J. of Combin.
• Strong edge-coloring of planar graphs with large girth (With Lily Chen, Kecai Deng and Xiangqian Zhou), Discrete Math.
• 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.
• The strong chromatic index of (3,\Delta)-bipartite graphs (with Minfang Huang and Xiangqian Zhou), Discrete Math., 340 (2017), no. 5, 1143--1149.
• Strong chromatic index of subcubc planar multigraphs (with A.V. Kostochka, X. Li, W. Ruksasakchai, M. Santana, T. Wang), European J. Combin. 51, (2016) 380--397.
• Strong edge-colorings of k-degenerate graphs, Graphs and Combin., 31 (2015), no. 5, 1815--1818.

Relaxed coloring (to Steinberg Conjecture, Bordeaux Conjecture et al)

• Planar graphs without $C_5$ and $K_4^-$ and adjacent $4$-cycles are $(2,0,0)$-colorable (with Xiangwen Li and Yuxue Yin), to appear at Discrete Math.
• Planar graphs without $4$-cycles and intersecting triangles are $(1,1,0)$-colorable (with Runrun Liu and Xiangwen Li), submitted.
• Planar graphs with girth at least $5$ are $(3,4)$-colorable (with Ilkyoo Choi and Xia Zhang), Discrete Math.
• Planar graphs without 4-cycles and close triangles are (2,0,0)-colorable, (with Heather Hoskins^*, Runrun Liu^**, Jennifer Vandenbussche), J. of Comb. Optim.,
• 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)
• 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.
• Planar graphs without 5-cycles and intersecting triangles are (1,1,0)-colorable (with Runrun Liu^** and Xiangwen Li). Discrete Math. 339 (2016), no. 2, 992--1003.
• A relaxation of the Bordeaux Conjecture (with Runrun Liu^** and Xiangwen Li), European J. Combin. 49 (2015), 240--249.
• Planar graphs without 4- or 5-cycles are (3,0,0)-colorable (with O. Hill^*, J. Xu, D. Smith, Y. Wang), Discrete Math., 313 (2013), no. 20, 2312--2317.
• A relaxation of Steinberg's Conjecture (with O. Hill^*), SIAM J. of Discrete Math 27 (2013) 584--596.

Other colorings

• 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)
• Linear colorings of subcubic graphs (with Chun-Hung Liu), European J. of Combinatorics 34 (2013) 1040-1050.
• Equitable coloring sparse planar graphs (with R. Luo, J.-S. Sereni, and C. Stephen) SIAM J. Discrete Math 24 (2010) 1572-1583.
• Injective colorings of sparse graphs (with D. Cranston and S.-J. Kim) Discrete Math. 310 (2010) 2965--2973.
• Linear Choosability of Sparse Graphs (with D. Cranston) Discrete Math. 311 (2011), no. 17, 1910--1917.

Routing number (diameter of Cayley graphs)

• 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.
• An Extremal problem on group connectivity of graphs (with R. Luo, R. Xu) European J. Combinaotorics, 33 (2012) 6, 1078-1085.
• Permutations as product of parallel transpositions (with C. Albert, C.-K. Li, and G. Strang) SIAM J. Discrete Math. 25 (2012), 1412-1417.

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.

Research related to computer sciences

• Optimal open-locating-dominating sets in infinite triangular grids (with Rex Kincaid, Allison Oldham^*), Discrete Appl. Math. 193 (2015), 139--144.
• New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid (with A. Cukierman^*), Disc. App. Math., 161 (2013), no. 18, 2910--2924.
• Toward Efficient Channel Hopping for Communication Rendezvous in Dynamic Spectrum Access Networks (with Y. Zhang^**, Q. Li, H. Wang, G. Zhu, and B. Wang), IEEE/ACM Transactions on Networking 22 (3), 889--902

Other topics (flow and group connectivity, routing number, et al)