On incidence coloring of graph fractional powers

Opuscula Mathematica

article

Mahsa Mozafari-Nia¹  Moharram N. Iradmusa (corresponding author)¹ 

[1]Shahid Beheshti University, Department of Mathematical Sciences

关键词: incidence coloring;    incidence chromatic number;    subdivision of graph;    power of graph.;   

DOI  :  10.7494/OpMath.2023.43.1.109

学科分类：环境科学（综合）

来源: AGH University of Science and Technology Press

【 摘 要 】

For any \(n\in \mathbb{N}\), the \(n\)-subdivision of a graph \(G\) is a simple graph \(G^\frac{1}{n}\) which is constructed by replacing each edge of \(G\) with a path of length \(n\). The \(m\)-th power of \(G\) is a graph, denoted by \(G^m\), with the same vertices of \(G\), where two vertices of \(G^m\) are adjacent if and only if their distance in \(G\) is at most \(m\). In [M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), no. 10-11, 1551-1556] the \(m\)-th power of the \(n\)-subdivision of \(G\), denoted by \(G^{\frac{m}{n}}\) is introduced as a fractional power of \(G\). The incidence chromatic number of \(G\), denoted by \(\chi_i(G)\), is the minimum integer \(k\) such that \(G\) has an incidence \(k\)-coloring. In this paper, we investigate the incidence chromatic number of some fractional powers of graphs and prove the correctness of the incidence coloring conjecture for some powers of graphs.

【 授权许可】

CC BY-NC