具有较小直径的三类图的对极色数

对一个连通图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.

Antipodal Chromatic Number of Three Classes of Graphs with Small Diameter

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 small diameter d.