HOSIGRA

One can view the following as a general definition of chromatic number:

Given a homomorphism property P and a graph or a signed graph G satisfying P, the smallest order of vertices of a homomorphic image of G also satisfying P is said to be P-chromatic number of G or simply the chromatic number of G when the property P is clear from the context.

For example classic chromatic number of a simple graphs is the P-chromatic number where P is the property of being loop-free.

For another example: if P is the property of being triangle-free, then a result of R. Naserasr is that every triangle-free planar graph has a P-chromatic number at most 16 (the 16 vertices graph built on the logo of site works as a universal image). Another result of the same author shows 16 is the best possible for this class of graphs.

We then have a large number of parameters to work with. The definition of chromatic of signed graphs given in "R. Naserasr, E. Rollová and É. Sopena. Homomorphisms of planar signed graphs to signed projective cubes. Discrete Math. Theoret. Comput. Sci. 15(3):1–12, 2013." is the P-chromatic number where P is the property of having g₀₁, g₁₁, g₁₀ ≥ 3 (noting that parity implies g₁₀ ≥ 4). Observe that this would be working with signed graphs where underlying graphs are simple.

If we relax our condition in the target and allow g₁₁=1, g₁₀=2, then we have a definition of the chromatic number of signed graphs given by Zaslavsky.

By selecting a definition we have a new graph parameter to work on. The most natural class of graphs to try the parameter is the class of planar signed graphs. We have the following questions in special cases:

• Both input and target are signed graphs where underlying graphs are simple, that is to say g₀₁, g₁₁, g₁₀ ≥ 3. In this case, for the class of signed planar graphs we have a lower bound of 10 given in "R. Naserasr, E. Rollová and É. Sopena. Homomorphisms of signed graphs. J. Graph Theory 79(3):178-212, 2015." and an upper bound of 40 given in "P. Ochem, A. Pinlou, and S. Sen. Homomorphisms of 2-edge-colored triangle-free planar graphs. J. Graph Theory, 85(1):258-277, 2017." Furthermore, it is proved in the latter that if the lower bound of 10 is the right bound, then the universal target on 10 vertices is built from signed Paley graph on 9 vertices by adding a vertex which is adjacent to all 9 vertices with a positive edge.
  
  
• Inputs are signed graphs with underlying simple graph, but the target is allowed to have negative loops and digons however no positive loop is allowed. In this case a conjecture of A. Raspaud claims that the two vertices graph obtained from digon by adding a negative loop to each vertex works. That is equivalent to saying:
  
  Conjecture 1 [A. Raspaud] Every singed planar graph can be resigned and then 2-colored such that each color class induces only negative edges.
  
  
• Similar conjecture for other restrictions can be proposed. We state only one reformulation of some:
  
  Conjecture 2 Every singed planar graph can be resigned and then 2-colored such that each color class induces only positive edges. (Equivalent to Conjecture 1 as only the role of signs have changed).
  
  Conjecture 3 [R. Naserasr] Every singed planar graph can be resigned and then 2-colored such that color class 1 induces only negative edges and color class 2 induces only positive edges.
  
  
• A common theme is the following relaxed conjecture:
  
  Conjecture 4 [R. Naserasr] Every singed planar graph can be 2-colored such that every unbalanced even-cycle is 2-colored.

Conjecture 4, if verified, would imply that for every planar signed graph at least one of the three conjectures (1--3) would hold.

A relation to list-coloring of planar graphs:

It is now well-known that not every planar graphs is 4-list colorable. The four-color theorem claims if all the lists are the same set of size four, then every planar graph admits a coloring. Kündgen and Ramamurthi proposed a half way conjecture. Given a planar graph G consider a list assignment L of colors to vertices where colors come in pairs of twins, that is to say whenever c is in L(v), then its twin color c' is also in L(v). The claim of the conjecture is that given a planar graph and for any such list assignment L, where each vertex receives a list of at least four colors (that is a pair of twin colors), G admits an L-coloring.

Xuding Zhu proved that Conjecture 1, if true, would imply the conjecture of Kündgen and Ramamurthi.

Extension of chromatic number to circular chromatic number:

A possible extension of a notion of chromatic number of signed graphs to circular chromatic number, based on the notion of chromatic number defined by Zaslavsky, is proposed and studied in "Y. Kang and E. Steffen, Circular coloring of signed graphs. J. Graph theory, 87(2):135–148, 2018." The authors then propose a conjecture on circular coloring of planar signed graphs which is can be restated as:
Conjecture 5 [Y. Kang and E. Steffen] Every singed planar graph can be resigned and then 3-colored such that color class 1 induces only negative edges and color classes 2 and 3 each induces no edge (they form independents set of the underlying graph).

Update Nov 2020:

Conjecture 1 is disproved by Kardos and Narbouni.

Conjecture 5 is disproved by X. Zhu.

Conjecture 3 is disproved by Naserasr and Pham. Furthermore, they determine for all but on signed graph on 3 vertices if it bounds the class of all signed planar simple graphs.