## “School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17143
 School of Mathematics Title: Simultaneous coloring of vertices and incidences of graphs Author(s): Moharram Nejad Iradmusa (Joint with Mahsa Mozafari-Nia) Status: Published Journal: Australas. J. Combin. Vol.: 85 Year: 2023 Pages: 287-307 Supported by: IPM
Abstract:
An $n$-subdivision of a graph $G$ is a graph constructed by replacing a path of length $n$ instead of each edge of $G$ and an $m$-power of $G$ is a graph with the same vertices as $G$ and any two vertices of $G$ at distance at most $m$ are adjacent. The graph $G^{\frac{m}{n}}$ is the $m$-power of the $n$-subdivision of $G$. In [M. N. Iradmusa, M. Mozafari-Nia, A note on coloring of $\frac{3}{3}$-power of subquartic graphs, Vol. 79, No.3, 2021] it was conjectured that the chromatic number of $\frac{3}{3}$-power of graphs with maximum degree $\Delta\geq 2$ is at most $2\Delta+1$. In this paper, we introduce the simultaneous coloring of vertices and incidences of graphs and show that the minimum number of colors for simultaneous proper coloring of vertices and incidences of $G$, denoted by $\chi_{vi}(G)$, is equal to the chromatic number of $G^{\frac{3}{3}}$. Also by determining the exact value or the upper bound for the said parameter, we investigate the correctness of the conjecture for some classes of graphs such as $k$-degenerated graphs, cycles, forests, complete graphs and regular bipartite graphs. In addition, we investigate the relationship between this new chromatic number and the other parameters of graphs.