We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Complex and Homomorphic Chromatic Number of Signed Planar Simple Graphs.
- Authors
Naserasr, Reza; Pham, Lan Anh
- Abstract
We introduce the notion of complex chromatic number of signed graphs as follows: given the set C k , l = { ± 1 , ± 2 , ... , ± k } ∪ { ± 1 i , ± 2 i , ... , ± l i } , where i = - 1 , a signed graph (G , σ) is said to be (k, l)-colorable if there exists a mapping c of vertices of G to C k , l such that for every edge xy of G we have c (x) c (y) ≠ σ (x y) | c (x) 2 |. The complex chromatic number of a signed graph (G , σ) , denoted χ com (G , σ) , is defined to be the smallest order of C k , l such that (G , σ) admits a (k, l)-coloring. In this work, after providing an equivalent definition in the language of homomorphisms of signed graphs, we show that there are signed planar simple graphs which are not 4-colorable. That is to say: there is a signed planar simple graph which is neither (2, 0)-colorable, nor (1, 1)-colorable, nor (0, 2)-colorable. That every signed planar simple graph is (2, 0)-colorable was the subject of a conjecture by Máçajová, Raspaud and Škoviera which was recently disproved by Kardoš and Narboni using a dual notion. We provide a direct approach and a short proof. That every signed planar simple graph is (1, 1)-colorable is a recent conjecture of Jiang and Zhu which we disprove in this work. Noting that (0, 2)-coloring of (G , σ) is the same as (2, 0)-coloring of (G , - σ) , this proves the existence of a signed planar simple graph whose complex chromatic number is larger than 4. Further developing the homomorphism approach, and as an analogue of the 5-color theorem, we find three minimal signed graphs each on three vertices, without a K 1 ± (a vertex with both a positive and a negative loop) and each having the property of admitting a homomorphism from every signed planar simple graph. Finally we identify several other problems of high interest in colorings and homomorphisms of signed planar simple graphs.
- Subjects
HOMOMORPHISMS; PLANAR graphs; LOGICAL prediction
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-021-02433-3