“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17111
School of Mathematics
  Title:   Simultaneous coloring of vertices and incidences of outerplanar graphs
  Author(s):  Moharram Nejad Iradmusa (Joint with Mahsa Mozafari-Nia)
  Status:   Published
  Journal: Electronic Journal of Graph Theory and Applications (EJGTA)
  Vol.:  11
  Year:  2023
  Pages:   41-58
  Supported by:  IPM
  Abstract:
A $vi$-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)\cup I(G)$ receive distinct colors, where $I(G)$ is the set of incidences of $G$. The $vi$-simultaneous chromatic number, denoted by $\chi_{vi}(G)$, is the smallest integer $k$ such that $G$ has a $vi$-simultaneous proper $k$-coloring. In [M. Mozafari-Nia, M. N. Iradmusa, A note on coloring of $\frac{3}{3}$-power of subquartic graphs, Vol. 79, No.3, 2021] $vi$-simultaneous proper coloring of graphs with maximum degree $4$ is investigated and they conjectured that for any graph $G$ with maximum degree $\Delta\geq 2$, $vi$-simultaneous proper coloring of $G$ is at most $2\Delta+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 $vi$-simultaneous chromatic number of any outerplanar graph $G$ is either $\Delta+2$ or $\Delta+3$, where $\Delta$ is the maximum degree of $G$.

Download TeX format
back to top
scroll left or right