对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.
For a connected graph G, let d(u, v) denote the distance between two vertices u and v of G, and d be the diameter of G. An antipodal coloring c of G is an assignment of positive integers (colors) to the vertices of G, such that d(u, v) + │c(u) - c(v)│ 〉 d for every pair u and v of distinct vertices of G. The value ac(c) is the maximum color assigned to a vertex of G by c, the antipodal chromatic number ac(G) of G is the minimum of ac(c) taken over all antipodal coloring c of G. In this paper, we determine the exact values of antipodal chromatic number for wheel graphs, gear graphs and double star graphs, which all have smalldiameter d.