COLORING PROBLEM OF SIGNED INTERVAL GRAPHS

We consider simple graphs G = (V;E), i.e graphs without loops and multiple edges. A graph G together with a function s : E 􀀀! f+; 􀀀g on the edge set of G is called a signed graph. If is the set of edges whose image under s is 􀀀 , then we denote the signed graph by = (G; ). The graph G is called the ground of and the set is called the signature of it. For any edge e of , we call it a positive or negative edge if s(e) has positive or negative sign respectively. By the edge and vertex set of we mean those of the ground graph that are V;E respectively. For a signed graph = (G; ) by the positive (negative ) subgraph we mean the spanning subgraph of G where the edge set is the set of positive (negative) edges of and is denoted by + (􀀀).