Simultaneous coloring of vertices and incidences of outerplanar graphs
Mahsa Mozafari-Nia, Moharram N. Iradmusa · Electronic Journal of Graph Theory and Applications · 2023
A v i -simultaneous proper k -coloring of a graph G is a coloring of all vertices and incidences of the graph in which any two adjacent or incident elements in the set V ( G )∪ I ( G ) receive distinct colors, where I ( G ) is the set of incidences of G . The v i -simultaneous chromatic number, denoted by χ v i ( G ) , is the smallest integer k such that G has a v i -simultaneous proper k -coloring. In [M. Mozafari-Nia, M. N. Iradmusa, A note on coloring of 3/3 -power of subquartic graphs, Vol. 79, No.3, 2021] v i -simultaneous proper coloring of graphs with maximum degree 4 is investigated and they conjectured that for any graph G with maximum degree Δ ≥ 2 , v i -simultaneous proper coloring of G is at most 2 Δ + 1 . In [M. Mozafari-Nia, M. N. Iradmusa, Simultaneous coloring of vertices and incidences of graphs, arXiv:2205.07189, 2022] the correctness of the conjecture for some classes of graphs such as k -degenerated graphs, cycles, forests, complete graphs, regular bipartite graphs is investigated. In this paper, we prove that the v i -simultaneous chromatic number of any outerplanar graph G is either Δ + 2 or Δ + 3 , where Δ is the maximum degree of G .