Signed colouring and list colouring of k‐chromatic graphs. Issue 4 (8th October 2021)

• Record Type: Journal Article
• Authors: Kim, Ringi; Kim, Seog‐Jin; Zhu, Xuding
• Is Part Of: Journal of graph theory. Volume 99:Issue 4(2022)
• Page Start: 637
• Page End: 650
• Publication Date: 2021-10-08
• Subjects: signed chromatic number -- signed graph -- weak signed choice number; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22756
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A k ‐ colouring of a signed graph ( G, σ ) is a mapping f : V ( G ) → N k such that for each edge e = x y, f ( x ) ≠ σ ( e ) f ( y ), where N k is a symmetric integer set of size k (i.e., i ∈ N k implies that − i ∈ N k ). The signed chromatic number χ ± ( G ) of a graph G is 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 the 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 c h ± 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 c h ± w ( G ) − χ ± ( G ) can be arbitrarily large. On the other hand, c h ± w ( G ) is bounded from above by twice the list vertex arboricity of G . Using this result, we prove that c h ± w ( T ( 2 n, n ) ) = χ ± ( T ( 2 n, n ) ) = 2 n 3 + 2 n 3, where T ( 2 n, n ) is the complete n ‐partite graph with each partite set of size 2.