报告题目：A polynomial algorithm on strong edge coloring of K₄-minor free graphs

报告人：Ping Wang Professor，St. Francis Xavier University

报告时间：2024年12月24日（周二）18:30-19:30

报告地点：腾讯会议：519-747-751

报告摘要：The strong chromatic index χ_s’(G) of a graph G is the smallest integer k such that G has a proper edge k-coloring with the condition that any two edges at distance at most 2 receive distinct colors. It is known that  χ_s’(G)≤3∆-2 for any K₄-minor free graph G with ∆≥3 where ∆ denotes the maximum degree of G. We give a polynomial algorithm of order O(|E(G)|(n²∆²+2n²+16∆)) to generate a strong edge coloring of a K₄-minor free graph with 3∆-2 colors where ∆≥3.

报告人简介：Ping Wang，现为加拿大圣弗朗西斯泽维尔大学数学与统计学学院教授、博士生导师。主要从事图论以及算法应用方面的研究，包括图的染色、极值图论、算法应用、数据挖掘与金融数学等。至今在Journal of Graph Theory、Graph and Combinatoric、Discrete Mathematics、Advances in Mathematics、Applied Economics、《中国科学》（英文版）等国际国内著名刊物发表系列论文，主持参与中国自然科学基金（NSFC）与加拿大自然科学与工程研究基金（NSERC）项目等。

邀请人：王维凡