Coloring problem of signed interval graphs

A signed graph $(G,\sigma)$ is a graph‎ ‎together with an assignment of signs $\{+,-\}$ to its edges where‎ ‎$\sigma$ is the subset of its negative edges‎. ‎There are a few variants of coloring and clique problems of‎ ‎signed graphs‎, ‎which have been studied‎. ‎An initial version known as vertex coloring of signed graphs is defined by Zaslavsky in $۱۹۸۲$‎. ‎Recently Naserasr et. al., in [R‎. ‎Naserasr‎, ‎E‎. ‎Rollova and E‎. ‎Sopena‎, ‎Homomorphisms of signed graphs‎, ‎J‎. ‎Graph Theory‎, ۷۹‎‎ (۲۰۱۵) ۱۷۸--۲۱۲, have defined signed chromatic and signed clique numbers of signed graphs‎. ‎In this paper we consider the latter mentioned problems for signed interval graphs‎. ‎We prove that the coloring problem of signed‎ ‎interval graphs is NP-complete whereas their ordinary coloring‎ ‎problem (the coloring problem of interval graphs) is in P‎. ‎Moreover we prove that the signed clique problem of a‎ ‎signed interval graph can be solved in polynomial time‎. ‎We also consider the‎ ‎complexity of further related problems‎.

Keywords:

‎Signed clique Problem‎ , ‎Signed Interval Graphs‎ , ‎Signed Coloring Problem