On the $s$-coloring of signed graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, University of Kashmir, Srinagar, India

2 Staque Solutions, 940 6 Ave SW Suite 200 Calgary AB T2P 3T1, Canada

Abstract

The sign of a vertex in a signed graph be defined naturally as the product of signs of edges incident to the vertex. We say that an edge is {\it consistent} or a  $c$-edge if its end-vertices have the same sign. Over the years, different notions of vertex coloring have been defined for signed graphs. Here, we introduce a new type of coloring in which any two vertices joined by a $c$-edge are assigned different colors. We call this the $s$-coloring of a signed graph. The $s$-chromatic number $\chi _{s}(G)$ of a signed graph $G$ is the minimum number of colors required to properly $s$-color the vertices of $G$. We obtain several bounds for $\chi_{s}(G)$. We show that the number of $s$-colorings of a signed graph $G$ is a polynomial function of the number $k$ of colors, which we call the $s$-chromatic polynomial $S(G,k)$ of $G$. We define the operations of removal and compression to develop a deletion-contraction type recursive procedure for determining $S(G,k)$. We introduce the notions of $c$-complete and $c$-full signed graphs, characterizing different classes of $c$-full signed graphs and determining the number of $c$-complete signed graphs on a given number of vertices. Furthermore, the relationship between $s$-coloring and other signed graph colorings is also investigated.

Keywords

Main Subjects

References

[1] R. Behr, Edge coloring signed graphs, Discrete Math. 343 (2020), no. 2, Article ID: 111654. https://doi.org/10.1016/j.disc.2019.111654
[2] D. Cartwright and F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968), 85–89.
[3] F. Harary, Graph Theory, Addison-Wesley, 1971.
[4] R. Janczewski, K. Turowski, and B. Wróblewski, Edge coloring of graphs of signed class 1 and 2, Discrete Appl. Math. 338 (2023), 311–319.  https://doi.org/10.1016/j.dam.2023.06.029
[5] Y. Kang, Coloring of signed graphs, Phd thesis, Universität Paderborn, Paderborn, Germany, 2017.
[6] Y. Kang and E. Steffen, The chromatic spectrum of signed graphs, Discrete Math. 339 (2016), no. 11, 2660–2663.
https://doi.org/10.1016/j.disc.2016.05.013
[7] Y. Kang and E. Steffen, Circular coloring of signed graphs, J. Graph Theory 87 (2018), no. 2, 135–148. https://doi.org/10.1002/jgt.22147
[8] F. Kardoš and J. Narboni, On the 4-color theorem for signed graphs, European J. Combin. 91 (2021), Article ID: 103215.  https://doi.org/10.1016/j.ejc.2020.103215
[9] E. Máčajová, A. Raspaud, and M. Škoviera, The chromatic number of a signed graph, Electron. J. Comb. 23 (2016), no. 1, 1–10.
[10] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient Black-Swan, Hyderabad, 2012.
[11] E. Steffen and A. Vogel, Concepts of signed graph coloring, European J. Combin. 91 (2021), Article ID: 103226.
https://doi.org/10.1016/j.ejc.2020.103226
[12] D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
[13] T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982), no. 2, 215–228.  https://doi.org/10.1016/0012-365X(82)90144-3
[14] T. Zaslavsky, How colorful the signed graph?, Discrete Math. 52 (1984), no. 2-3, 279–284. https://doi.org/10.1016/0012-365X(84)90088-8
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 28 April 2025

Files

Share

How to cite

Statistics