Research

Home

Research

Teaching

Some pictures

My area of interest in mathematics is graph theory and combinatorics. It is a beautiful and relatively young branch of mathematics which really only evolved seriously in its own right back in around the 1900’s, although many ideas in the area have existed much earlier. I very much appreciate the fact that ideas from almost all other areas of mathematics, such as analysis, topology, algebra, number theory, and probability, are involved in the area. Moreover, graph theory and combinatorics has applications to other subjects such as computer science and mathematical physics. For example, the latter includes the wonderful area of percolation theory.

My recent research include the following topics: Graph colourings, connectivity of graphs, extremal graph theory, and games on graphs. I have also worked on some of these topics in the directed graphs and hypergraphs settings.

My Erdős number is 2.

Curriculum Vitae

Research Papers

26. Cops and Robber on Cartesian products and some classes of hypergraphs (with Pinkaew Siriwong, Ratinan Boonklurb and Sirirat Singhun), submitted.

25. The size of graphs with restricted rainbow 2-connection number (with Shinya Fujita and Boram Park), Journal of Combinatorial Mathematics and Combinatorial Computing, 116 (2021), 183-200 (pdf, 284kb).
24. Gallai-Ramsey number for K₄ (with Colton Magnant, Akira Saito, Ingo Schiermeyer and Yongtang Shi), Journal of Graph Theory, 94 (2020), 192-205 (pdf, 283kb).
23. Degree powers in graphs with a forbidden forest (with Yongxin Lan, Zhongmei Qin and Yongtang Shi), Discrete Mathematics, 342 (2019), 821-835 (pdf, 350kb).
22. Turán function and H-decomposition problem for gem graphs (with Teresa Sousa), Discussiones Mathematicae Graph Theory, 38 (2018), 717-741 (pdf, 355kb).
21. Highly connected subgraphs of graphs with given independence number (with Shinya Fujita and Amites Sarkar), European Journal of Combinatorics, 70 (2018), 212-231 (pdf, 406kb).
20. On various (strong) rainbow connection numbers of graphs (with Lin Chen, Xueliang Li and Jinfeng Liu), The Australasian Journal of Combinatorics, 70 (2018), 137-156 (pdf, 271kb).
19. Total rainbow connection of digraphs (with Hui Lei, Colton Magnant and Yongtang Shi), Discrete Applied Mathematics, 236 (2018), 288-305 (pdf, 415kb).
18. Rainbow vertex connection of digraphs (with Hui Lei, Shasha Li and Yongtang Shi), Journal of Combinatorial Optimization, 35 (2018), 86-107 (pdf, 384kb).
17. Spectral conditions for some graph properties (with Lihua Feng, Pengli Zhang, Weijun Liu, Minmin Liu and Yuqin Hu), Linear Algebra and its Applications, 524 (2017), 182-198 (pdf, 254kb).
16. Decompositions of graphs into fans and single edges (with Teresa Sousa), Journal of Graph Theory, 85 (2017), 400-411 (pdf, 274kb).
15. Incidence graphs constructed from t-designs (with Xu Yang, Weijun Liu and Lihua Feng), Applicable Analysis and Discrete Mathematics, 10 (2016), 457-478 (pdf, 348kb).
14. The spectral radius of edge chromatic critical graphs (with Jianxiang Cao, Shifeng Ding, Lihua Feng and Weijun Liu), Linear Algebra and its Applications, 492 (2016), 78-88 (pdf, 254kb).
13. Monochromatic clique decompositions of graphs (with Oleg Pikhurko and Teresa Sousa), Journal of Graph Theory, 80 (2015), 287-298 (pdf, 264kb).
12. Monochromatic structures in edge-coloured graphs and hypergraphs - a survey (with Shinya Fujita and Colton Magnant), International Journal of Graph Theory and its Applications, 1 (2015), 3-56 (pdf, 392kb).
11. Rainbow k-connection in dense graphs (with Shinya Fujita and Colton Magnant), Journal of Combinatorial Mathematics and Combinatorial Computing, 93 (2015), 33-52 (pdf, 235kb).
10. Total rainbow k-connection in graphs (with Ângela Mestre and Teresa Sousa), Discrete Applied Mathematics, 174 (2014), 92-101 (pdf, 327kb).
9. Rainbow connection for some families of hypergraphs (with Rui Pedro Carpentier, Manuel Silva and Teresa Sousa), Discrete Mathematics, 327 (2014), 40-50 (pdf, 208kb).
8. Monochromatic K_r-decompositions of graphs (with Teresa Sousa), Journal of Graph Theory, 76 (2014), 89-100 (pdf, 188kb).
7. Rainbow vertex k-connection in graphs (with Ângela Mestre and Teresa Sousa), Discrete Applied Mathematics, 161 (2013), 2549-2555 (pdf, 180kb).
6. The balanced decomposition number of TK₄ and series-parallel graphs (with Shinya Fujita), Discussiones Mathematicae Graph Theory, 33 (2013), 347-359 (pdf, 188kb).
5. Further results on the balanced decomposition number (with Shinya Fujita), in Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 202 (2010), 119-128 (pdf, 360kb).
4. The balanced decomposition number and vertex connectivity (with Shinya Fujita), SIAM Journal on Discrete Mathematics, 24 (2010), 1597-1616 (pdf, 322kb).
3. Highly connected coloured subgraphs via the regularity lemma (with Yury Person), Discrete Mathematics, 309 (2009), 6277-6287 (pdf, 259kb).
2. Highly connected monochromatic subgraphs of multicoloured graphs (with Robert Morris and Noah Prince), Journal of Graph Theory, 61 (2009), 22-44 (pdf, 286kb).
1. Highly connected multicoloured subgraphs of multicoloured graphs (with Robert Morris and Noah Prince), Discrete Mathematics, 308 (2008), 5096-5121 (pdf, 328kb).

2. A new lower bound for the convex decomposition number of point sets in the plane, manuscript (pdf, 222kb).
1. Highly connected monochromatic subgraphs of multicoloured graphs: addendum (with Robert Morris and Noah Prince), manuscript (pdf, 158kb).

3. Highly connected subgraphs of graphs with given independence number (extended Abstract) (with Shinya Fujita and Amites Sarkar; short version of paper 21), in: Discrete Mathematics Days - JMDA16, Electronic Notes in Discrete Mathematics, 54 (2016), 103-108 (pdf, 217kb).
2. Monochromatic K_r-decompositions of graphs (extended abstract) (with Teresa Sousa; short version of paper 8), Electronic Notes in Discrete Mathematics, 43 (2013), 121-127 (pdf, 128kb).
1. Rainbow k-connection in dense graphs (extended abstract) (with Shinya Fujita and Colton Magnant; short version of paper 11), in: Proceedings of EuroComb '11, Electronic Notes in Discrete Mathematics, 38 (2011), 361-366 (pdf, 148kb).

PhD Dissertation

• Recent extremal problems in combinatorics, The University of Memphis (2006).

Master Level Theses

• Ergodic theory and Szemerédi's theorem (2001): My thesis when I did Part III of the Mathematical Tripos at University of Cambridge (pdf, 321kb).
• Discrete isoperimetric inequalities (2000): My thesis in my final year at University College London (pdf, 465kb).

Conference and Seminar Talks

• Degree powers in graphs with a forbidden forest (with Yongxin Lan, Zhongmei Qin and Yongtang Shi). Talk given at The Japanese Conference on Combinatorics and its Applications (JCCA 2018) in Sendai, Sendai, Japan, 20 to 24 May 2018; Topology and Combinatorics seminar, Ajou University, Suwon, South Korea, 21 August 2018; and AMS Sectional Meeting (Special Session on Structural Graph Theory), University of Hawaii at Manoa, Honolulu, USA, 22 to 24 March 2019. These slides are from the JCCA 2018 (pdf, 447kb).
• Highly connected subgraphs in sparse graphs (with Shinya Fujita and Amites Sarkar). Talk given at KAIST Discrete Math Seminar, KAIST, Daejeon, South Korea, 15 June 2017; The 16th KIAS Combinatorics Workshop, KIAS, Seoul, South Korea, 2 to 3 June 2017 (as an invited speaker); DPMMS Combinatorics Seminar, University of Cambridge, Cambridge, UK, 9 February 2017; The Third Sino-Japan Symposium on Graph Theory, Combinatorics and their Applications, Northwestern Polytechnical University, Xi’an, China, 3 to 6 November 2016; 2016 International Conference on Graph Theory, Combinatorics and Applications, Zhejiang Normal University, Jinhua, China, 28 to 31 October 2016 (as an invited speaker); and The Japanese Conference on Combinatorics and its Applications (JCCA 2016) in Kyoto, Kyoto University, Kyoto, Japan, 21 to 25 May 2016. These slides are from the JCCA 2016 (pdf, 369kb).
• Connected subgraphs in edge-coloured graphs (with Shinya Fujita and Colton Magnant). Talk given at Topology and Combinatorics seminar, Ajou University, Suwon, South Korea, 7 June 2017; Simon Fraser University Discrete Mathematics Seminar, Simon Fraser University, Burnaby, Canada, 10 March 2015; and Workshop on Graph Theory and Combinatorial Optimization, Nankai University, Tianjin, China, 14 to 15 November 2015 (as an invited speaker). These slides are from the seminar at SFU (pdf, 416kb).
• Rainbow connection in hypergraphs (with Rui Pedro Carpentier, Manuel Silva and Teresa Sousa). Talk given at Bordeaux Graph Workshop 2012, LaBRI, Université Bordeaux 1, Talence, France, 21 to 24 November 2012 (pdf, 792kb).
• Rainbow k-connection in dense graphs (with Shinya Fujita and Colton Magnant). Talk given at EuroComb '11, Eötvös Lorand University, Budapest, Hungary, 29 August to 2 September 2011 (pdf, 772kb).
• The balanced decomposition number of a graph (with Shinya Fujita). Talk given at 8th French Combinatorial Conference, Université de Paris XI - Sud, Orsay, France, 28 June to 2 July 2010; and 41st Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, USA, 8 to 12 March 2010. These slides are from the 8FCC (pdf, 489kb).
• Highly connected coloured subgraphs and the regularity lemma (with Yury Person). Talk given at Additive Combinatorics in Lisbon, Universidade de Lisboa, Lisbon, Portugal, 21 to 24 June 2010 (pdf, 778kb).
• Highly connected subgraphs in multicoloured graphs (with Robert Morris and Noah Prince). Talk given at Final COMBSTRU Workshop, Universitat Politècnica de Catalunya, Barcelona, Spain, 25 to 27 September 2006; Horizon of Combinatorics, Lake Balaton, Hungary, 16 to 22 July 2006; and PIMS-MITACS Summer School in Probability, University of British Columbia, Vancouver, Canada, 6 to 30 June 2005. These slides (reproduced from an old format) are from the Final COMBSTRU Workshop (pdf, 383kb).

Students

Doctoral Students

• Ting Lan / 兰婷 (Expected graduation July 2027).
• Yueping Shi / 史月萍 (Expected graduation July 2026).

Master Students

• Wenpei Li / 李文佩 (Expected graduation July 2026).
• Fengxiang Rao / 饶风翔 (Expected graduation July 2025).
• Chuang Li / 历闯 (Graduated July 2023).
• Jiayi Chang / 常佳艺 (Graduated July 2023).
• Chenming Wang / 王晨鸣 (Graduated July 2023).

Guangzhou Discrete Mathematics Seminar

Interesting Links

• Me at the Mathematics Genealogy Project.
• My profile and publications on MathSciNet. My name is listed as "Henry C. Liu" there.
• My profile at the research training network "Phenomena in High Dimensions", when I was appointed an Experienced Researcher in 2007/2008.