两圈卡氏积的单射染色

Injective Coloring of the Cartesian Product of Two Cycles

图的单射染色是指图的一种点染色,它要求有公共邻点的两个顶点需染不同颜色.图G的单射色数χi(G)就是指满足图G有一个单射的k-染色的最小的正整数k.本文讨论了两个圈的卡氏积的单射色数问题,并给出了χi(Tm,n)的一些紧的上界以及一些确切值,这里Tm,n=Cm□Cn,m≥3且n≥3.

An injective coloring of a graph is a vertex coloring such that any two different vertices with a common neighbor vertex receive distinct colors.The injective chromatic numberχi(G)is the least k such that the graph G has an injective k-coloring.In this paper,we investigate the injective chromatic number of the Cartesian product of two cycles and give some sharp bounds(or exact value)ofχi(Tm,n),where Tm,n=Cm□Cn,m≥3 and n≥3.