首 页 中心简介 成员介绍 学术交流 教育部重点实验室 科研动态 研究生培养 省数学会 English
发表日期:2017年6月23日      

新加坡南洋理工大学董峰明教授学术报告

 

报告人:董峰明,Nanyang Technological University, Singapore

报告时间:2017年6月27日16:00-18:00

报告地点:数计学院4号楼229室

报告题目:Chromatic polynomials of hypergraphs

报告摘要:For any graph G, the chromatic polynomial of G is a function P(G; \lambda) such that P(G; k) is the number of proper k-colourings of G for any positive integer k. This graph-function for planar graphs was originally introduced by George David Birkho in 1912 to attack the four color problem. Hassler Whitney generalised it from the planar case to general graphs in 1932. In 1968 Read asked which polynomials are the chromatic polynomials of some graphs, a question that remains open, and some other questions. Today, chromatic polynomial is one of the central objects of algebraic graph theory.

The graph-function P(G; \lambda) for graphs was extended to the case for hypergraphs in 1970s. A (simple) hypergraph \mathcal{H}=(\mathcal{V}, \mathcal{E}) consists of a vertex-set \mathcal{V}= \{v_1,...,v_n\} and an edge-set \mathcal{E} =\{e_1,...,e_m\} where e_i\subseteq \mathcal{V} and e_i\neq e_j for all 1\le i\le j. If |e_i|= 2 holds for each e_i\in\mathcal{E} , then \mathcal{H} is a simple graph. A (weak) proper\lambda-colouring of a hypergraph \mathcal{H} is a mapping f : \mathcal{V}\rightarrow \{1,...,\lambda\} such that |\{f(u) : u \in e\}|\ge 2 holds for each e\in \mathcal{E}. Let P(\mathcal{H}; \lambda) be the number of perper \lambda-colourings of \mathcal{H}. This graph-function P(\mathcal{H}; \lambda) is a polynomial of \lambda with degree |\mathcal{V}| and is called the chromatic polynomial of \mathcal{H}. Clearly P(\mathcal{H}; \lambda) is an extension of chromatic polynomials of simple graphs. In this talk, we will present our latest results on some properties of P(H; ) which are different from properties of chromatic polynomials of graphs. We will also introduce some open problems on the study of P(\mathcal{H}; \lambda).

Joint work with Zhang Ruixue, Nanyang Technological University, Singapore.


相关信息:
 没有相关信息

 
 
 

| 加入收藏 | 设为首页 | 管理系统 |


版权所有: 福州大学离散数学与理论计算机科学研究中心
地址:福建省福州市福州地区大学新区学园路2号   邮编:350116
联系电话: 0591-83058092 ,83846655
传真:0591-83846622  E-mail: dimacs@fzu.edu.cn