IBS/KAIST Joint Discrete Math Seminar

Signed colouring and list colouring of k-chromatic graphs

2019/1/28 Mon 4PM-5PM (Room B232, IBS)

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) → N

_{k} such that for each edge e=uv, f(x)≠σ(e) f(y), where N

_{k} 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}(K

_{2⋆n})= χ

_{±}(K

_{2⋆n}) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.