Simultaneous coloring of vertices and incidences of hypercubes

Document Type : Original paper

Authors

Department of Mathematical Sciences, Shahid Beheshti University.

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

References

[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
 
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 67-77

Files

Share

How to cite

Statistics