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 χ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 χ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