【华中师范大学】Decomposing graphs of nonnegative characteristic into subgraphs with degree restrictions

报告题目：Decomposing graphs of nonnegative characteristic into subgraphs with degree restrictions

报告人：李相文 教授（华中师范大学）

报告时间：2023年8月18日（星期五）14:30-15:20

报告地点：海山楼（创新园大厦）A1101

校内联系人：王毅 教授

报告摘要:A (d,h)-decomposition of G is a pair (H1,H2) such that H2 is a subgraph of G of maximum degree at mosthand H1 is d-degenerate such that H1 = G−E(H2). A graph G is (d,h)-decomposable if G has a (d,h)-decomposition. A graph G is a NC-graph if it can be embedded in a surface of nonnegative characteristic. In this paper, we prove the following results. (1) Every NC-graph G is (4,2)-decomposable. Moreover, G is (4,1)-decomposable if and only if G is not 6-regular triangulation, which generalizes a result of Cho, Choi, Kim, Park, Shan, Zhu [J. Graph Theory, 101 (2020) 165–181]. (2) Every NC-graph is (5,1)-decomposable. (3) Every NC-graph is (2,8)- or (3,4)-decomposable, which generalizes a result of Zhu [Discrete Math., 215 (1) (2000) 245–262] and a result of Goncalves [J. Combin. Theory Ser. B., 99 (2) (2009) 314–322]. This work is joint with Lin Niu.

报告人简介：李相文，华中师范大学教授，博士生导师。博士毕业于美国西弗吉尼亚大学，加拿大里贾纳大学博士后。主要从事图论和组合优化方面的研究工作。研究领域包括图的染色，整数流与圈覆盖，超欧拉图及其相关问题。现在担任中国工业与应用学会图论与组合专业委员会常务委员。主持国家自然科学基金面上项目3项，作为主要成员参与国家基金重点项目1项，国家自然基金海外项目1项，主持教育部博士点基金1项，海外留学基金1项。在《Journal of Graph Theory》、《European Journal of Combinatorics》等国际权威杂志发表学术论文80多篇。