آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,538 |
| تعداد مشاهده مقاله | 1,628,302 |
| تعداد دریافت فایل اصل مقاله | 1,525,833 |
On the $s$-coloring of signed graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 08 اردیبهشت 1404 اصل مقاله (453.8 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30278.2395 | ||
| نویسندگان | ||
| Shariefuddin Pirzada* 1؛ Muhammad A. Khan2 | ||
| 1Department of Mathematics, University of Kashmir, Srinagar, India | ||
| 2Staque Solutions, 940 6 Ave SW Suite 200 Calgary AB T2P 3T1, Canada | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Signed graph؛ signed graph coloring؛ chromatic number؛ chromatic polynomial؛ deletion-contraction | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 205 تعداد دریافت فایل اصل مقاله: 146 |
||