University of Isfahan Transactions on Combinatorics 2251-8657 8 4 2019 12 01 Coloring problem of signed interval graphs 1 9 23849 10.22108/toc.2019.108880.1541 EN Farzaneh Ramezani Faculty of Mathematics, K. N. Toosi University of Technology, Tehran, Iran Journal Article 2018 03 03 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 $1982$‎. ‎Recently Naserasr et. al., in [R‎. ‎Naserasr‎, ‎E‎. ‎Rollova and E‎. ‎Sopena‎, ‎Homomorphisms of signed graphs‎,<em> ‎J‎. ‎Graph Theory</em>‎, <strong>79</strong>‎‎ (2015) 178--212, 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‎.<br /> <br /><br /> https://toc.ui.ac.ir/article_23849_1554f4e5c9d7ae542ab410c68865a403.pdf