Simultaneous coloring of vertices and incidences of hypercubes

Document Type : Original paper

Authors

Department of Mathematical Sciences, Shahid Beheshti University G.C., P.O. Box 19839-63113, Tehran, Iran

Abstract

An element $i=(v,e)$ of a graph $G$ is called  an incidence of $G$, if $v\in V(G)$, $e\in E(G)$ and $v\in e$. The simultaneous coloring of vertices and incidences of a graph is coloring  the vertices and incidences of the graph properly at the same time such that any two adjacent or incident elements receive distinct colors. In this paper, we investigate the simultaneous coloring of vertices and incidences of hypercubes.

Keywords

Main Subjects


[1] R.A. Brualdi and J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), no. 1-3, 51–58.
https://doi.org/10.1016/0012-365X(93)90286-3
[2] P. Gregor, B. Lužar, and R. Soták, On incidence coloring conjecture in cartesian products of graphs, Discrete Appl. Math. 213 (2016), 93–100.
https://doi.org/10.1016/j.dam.2016.04.030
[3] M. Mozafari-Nia and M. Nejad Iradmusa, A note on coloring of $3/3$-power of subquartic graphs, Australas. J. Combin. 79 (2021), no. 3, 454–460.
[4] M. Mozafari-Nia and M. Nejad Iradmusa, Simultaneous coloring of vertices and incidences of graphs, Australas. J.
Combin. 85 (2023), no. 3, 287–307.
[5] M. Mozafari-Nia and M. Nejad Iradmusa, Simultaneous coloring of vertices and incidences of outerplanar graphs,
Electron. J. Graph Theory Appl. 11 (2023), no. 1, 245–262.
https://dx.doi.org/10.5614/ejgta.2023.11.1.20
[6] M. Nejad Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), no. 10–11, 1551–1556.
https://doi.org/10.1016/j.disc.2010.01.017
[7] M. Nejad Iradmusa, A short proof of 7-colorability of $3/3$-power of sub-cubic graphs, Iran. J. Sci. Technol. Trans. A Sci. 44 (2020), no. 1, 225–226.
https://doi.org/10.1007/s40995-020-00819-1
[8] K.J. Pai, J.M. Chang, J.S. Yang, and R.Y. Wu, Incidence coloring on hypercubes, Theoret. Comput. Sci. 557 (2014), 59–65.
https://doi.org/10.1016/j.tcs.2014.08.017
[9] P.K. Sun, Incidence coloring of regular graphs and complement graphs, Taiwanese J.M. 16 (2012), no. 6, 2289–2295.
https://doi.org/10.11650/twjm/1500406852
[10] F. Wang and X. Liu, Coloring 3-power of 3-subdivision of subcubic graph, Discrete Math. Algorithms Appl. 10 (2018), no. 3, Article ID: 1850041.
https://doi.org/10.1142/S1793830918500416