當前位置: 湖北11选5开奖结果 / 科研學術 / 學術預告 / 正文

Critical permutation sets for generalized signed graph colouring

作者:   時間:2019-09-12   點擊數:

報告題目:Critical permutation sets for generalized signed graph coloring

 

報告人:齊豪  臺灣中研院博士后

 

摘要:Assume G is a graph and k is a positive integer. We view G as a symmetric digraph, in which each edge uv of G is replaced by a pair of opposite arcs e=(u,v) and $e^{-1}=(v,u)$. Let S be a set of permutations on [k] that is inverse closed. An S-signature of G is a mapping $\sigma: E(G)S$ for which $\sigma_{e^{-1}}=\sigma_{e}^{-1}$. The pair $(G, \sigma)$ is called a generalized signed graph. A k-coloring of $(G, \sigma)$ is a mapping $\varphi: V(G)[k]$ such that for each arc $e=(u,v)$, $\sigma_{e}(\varphi(u)) \neq \varphi(v)$. We say G is S-k-colorable if for any S-signature $\sigma$ of G, $(G,\sigma)$ is k-colorable. If $S={id}$, then S-k-colorable is the same as k-colorable. If $S=S_{k}$, then S-k-colorable is equivalent to DP-k-colorable. For other inverse closed sets S of permutations, S-k-colorability reveals a complex hierarchy of colorability of graphs. We say an inverse closed subset S of $S_{k}$ is critical if for any inverse closed subset $S^{’}$ containing S as a proper subset, there is a graph G which is S-k-colorable but not $S^{’}$-k-colorable. For a set X, denote by $S_{X}$ the symmetric group of all permutations on X. In this paper, we prove the following results: Assume [k] is the disjoint union of $X_1, X_2, \cdots, X_q$. If $S=\Gamma_1 \times \Gamma_2 \times \cdots \Gamma_q $, where for each i, either $\Gamma_i=S_{X_{i}}$ or $\mid X_{i} \mid=3$ and $\Gamma_i$ is the subgroup of $S_{X_{i}}$ generated by a cyclic permutation of $X_{i}$, then S is critical. This is joint work with Tsai-Lien Wong and Xuding Zhu.

 

時間:2019917日(星期二)9:00-10:00

 

地點:知新樓B1032報告廳

 

邀請人:吳建良教授

 

地址:中國山東省濟南市山大南路27號   郵編:250100  

電話:0531-88364652   投稿信箱:mathweb@sdu.edu.cn

Copyright@山東大學數學學院

微信公眾號
湖北11选5开奖结果