IPM - Institute for Research in Fundamental Sciences

“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:

$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.

Download TeX format

“School of Mathematics”

People

Schools

Centers

Groups

E-Services

Publications