◈ 학술지
◈ 도서
◈ 전자학술지
◈ 투고요령
◈ 수학신간도서
◈ MSC
◈ 논문검색
◈ 학술행사
홈 > 학술정보 >학술행사 > 세미나
KAIST Discrete Math 세미나

Title
Signed colouring and list colouring of k-chromatic graphs
Speaker
김석진   (건국대 )
Date
2019-01-28 16:00:00
Host
IBS
Place
Room B232, IBS (기초과학연구원)
Abstract
A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring. Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.
개인정보보호정책 l 이메일주소집단수집금지 l 뷰어다운로드
qr코드