Chromatic Number Of Signed Bipartite Graphs
Given an integer k we define CBk to be the signed bipartite graph build as follows
- One part is a set X of size k.
- The other part is all 2-partitions {A,X-A} of X
(thus {A,X-A} and {X-A, A} are the same vertices, but one of the parts is fixed as A). - An element x of X is adjacent to {A,X-A} with a positive edge if it is in A and with a negative edge if it is in X-A.
Given a signed bipartite graph (G, 𝛴 ) its (bipartite) chromatic number is the smallest k such that (G, 𝛴 )--> CBk.
The definition is rather new, one may restrict more by choosing which of the two parts of G must be mapped to the part X. It follows from a strengthening of the four-color theorem that bipartite-chromatic number of signed bipartite planar graphs is at most 4, the stronger statement is:
Theorem. Every planar signed bipartite graph maps to (K4, M).
One of the first natural questions is: is the statement every planar signed bipartite graph has (bipartite) chromatic number 4 stronger than the four-color theorem or it could be proved independently? More generally, is there an analogue of Hadwiger conjecture for this notion?
Another natural question: Can chromatic number of a graph G be expressed as the bipartite chromatic number of some bipartite signed graph associated to G?