-
Distance colorings of the semistrong product and the strong product of paths
- TIAN Shuangliang, CHEN Ping
-
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE). 2025, 60(12):
167-172.
doi:10.6040/j.issn.1671-9352.0.2024.094
-
Abstract
(
123 )
PDF (792KB)
(
32
)
Save
-
References |
Related Articles |
Metrics
A k-distance coloring of a graph G is a vertex coloring of G such that no two vertices lying at distance less than or equal to k in G are assigned the same color. The k-distance chromatic number of G, denoted χk(G), is the minimum number of colors needed for a k-distance coloring of G. The semistrong product of simple graphs G and H is the graph G·H with vertex set V(G)×V(H), in which (u,v) is adjacent to (u',v') if and only if either uu'∈E(G) and vv'∈E(H) or u=u' and vv'∈E(H). The strong product of simple graphs G and H is the graph GH with vertex set V(G)×V(H), in which (u,v) is adjacent to (u',v') if and only if uu'∈E(G) and vv'∈E(H), or u=u' and vv'∈E(H), or v=v' and uu'∈E(G). In this paper, for any integer k≥2, the k-distance chromatic numbers of the semistrong product and the strong product of two paths are obtained.