一类整数距离图的点荫度

徐 莉，左连翠

（天津师范大学 数学科学学院，天津 300387）

一类整数距离图的点荫度

徐 莉，左连翠

（天津师范大学 数学科学学院，天津 300387）

整数距离图以全体整数作为顶点集，顶点u、v相邻当且仅当u－v∈D，其中D是一个正整数集.对于m＞3，令Dm＝［1，m］＼［1，3］.本研究得到了G（Dm）的点荫度.

整数距离图；点荫度；树染色；正常染色；点色数

1 预备知识

引理2 假设有3个点b1＜b2＜b3在图G（Dm）的一个树染色中染了同一种颜色，则有

1）若存在一条同色（b1，b2）－路，则b3∈｛b1＋i，b2＋i｜i∈［1，3］｝或者b3≥b1＋（m＋1）；

2）若存在一条同色（b1，b3）－路，并且b3－b1≤m，则b2∈｛b1＋i，b3－i｜i∈［1，3］｝；

3）若存在一条同色（b2，b3）－路，则b1∈｛b2－i，b3－i｜i∈［1，3］｝或者b1≥b3－（m＋1）.

证明 1）否则，若b3∉｛b1＋i，b2＋i｜i∈［1，3］｝，并且b3＜b1＋（m＋1），则b1b3、b2b3∈E（G），从而（b1，b2）－路和2条边b1b3、b2b3形成一个圈，矛盾.2）和3）同理可证.引理证毕.

若6个点vi（i∈［0，5］）染了同色β，且满足：v2－v1＝v3－v2＝v4－v3＝1，min｛v1－v0，v5－v4｝≤2，v1－v0、v5－v4∈［1，3］，v5－v0∈［5，7］，则这样的一个集合｛vi｜i∈［0，5］｝称为一个由β和v0决定的F－型集.在不引起混淆的情况下，简称为F－型集.

引理3 若Vβ是一个由β和v0决定的F－型集，则在G（Dm）的一个树着色f中，对任意i∈［6，m＋4］＼｛vj｜j∈［0，5］｝，有f（v0＋i）≠β.

证明 否则，设对于某个i∈［6，m＋4］＼｛vj｜j∈［0，5］｝，有f（v0＋i）＝β.因为v0＝v与v4和v5都相邻，则由引理2，有v＋i∈｛v4＋j，v5＋j｜j∈［1，3］｝或者v＋i≥v4＋（m＋1）.因为m≥8，所以v0、v5、v1、v＋i导出一个4－圈，或者v1、v5、v2、v＋i导出一个4－圈，或者v2、v5、v3、v＋i导出一个4－圈，或者v0、v5、vj、v＋i、v4导出一个5－圈（其中j∈［1，3］），或者v＋i≥v4＋（m＋1）.从而v＋i≥v＋m＋4，这是不可能的.引理证毕.

引理4 在G（Dm）的树着色f中，若顶点a0＜a1＜…＜a5得到同色，且a5－a0≤m，则｛ai｜i∈［0，5］｝是一个F－型集.

证明 显然，若下列断言成立，则引理得证.

断言1a0a4、a0a5、a1a5∈E（G）.显然有 min｛a4－a0，a5－a1｝≥4，从而a0a4、a0a5、a1a5∈E（G）.

断言2a2－a1＝a3－a2＝a4－a3＝1.假若 max｛a2－a1，a3－a2，a4－a3｝≠1，则由断言1可知，a0、a4、a1、a5导出一个4－圈，矛盾.从而断言2成立.

断言3a1－a0、a5－a4∈［1，3］.若a1－a0＞3，则由断言2可知a0、a1、a5导出一个三角形，矛盾.因此a1－a0∈［1，3］.同理可证a5－a4∈［1，3］.

断言4a1－a0＋a5－a4≤4.否则，即a1－a0＋a5－a4≥5，由断言3有a1－a0＝3或者a5－a4＝3，那么a0、a2、a5导出一个三角形，或者a0、a3、a5导出一个三角形，矛盾.

综上，｛ai｜i∈［0，5］｝是一个F－型集.引理证毕.

引理5 在G（Dm）的树着色f中，若顶点0≤a0＜a1＜…＜a6≤m＋4着同色，则对于i＝0、1，有ai＋5－ai＞m.

证明 假设a5－a0≤m，则由引理4知，｛ai｜i∈［0，5］｝是一个F－型集，因此a0a4、a0a5、a1a5∈E（G），且由a6－a4≤m及引理2知a6∈｛a5＋i｜i∈［1，3］｝，那么a0、a5、a1、a6导出一个4－圈，或者a0、a4、a6、a5

2 G（Dm）的点荫度

断言a0＝0，a1＝1，a3＝m＋1，a4＝m＋2，a5＝m＋3且a6＝m＋4.

通过2个子断言来证明该断言.

子断言1a0＝0，a1＝1，a5＝m＋3且a6＝m＋4.

1）设a5＝m＋1.则由引理5知，a0a4∈E（H）且a0＝0.进而有a3∈｛a0＋i，a4－i｜i∈［1，3］｝.

若a3∈｛a0＋i｜i∈［1，3］｝，则a3＝3且a1a5、a2a5、a3a5∈E（H），那么a4＝4或者a4∈｛a5－i｜i∈［1，3］｝.若a4＝4，则有a4a5、a4a6∈E（H），从而a3a6∉E（H），即a6＝m＋4.此时由引理5知，在H中有n－1种颜色染［5，m］∪［m＋2，m＋3］中的m－2个点，使得每一种颜色恰染满足v5－v0≤7的6个点v0（≥5）、v1、v1＋1、v1＋2、v1＋3、v5.那么由引理4知，顶点m＋8、m＋9只能染α色，而它们与a5、a6导出一个4－圈，矛盾.若a4∈｛a5－i｜i∈［1，3］｝，则a4≥m－2，从而a1a4、a1a5、a2a4、a2a5∈E（H），即顶点a1、a4、a2、a5导出一个4－圈，矛盾.

若a3∈｛a4－i｜i∈［1，3］｝＼｛a0＋i｜i∈［1，3］｝，则a3≥4，a4－a3≤3，且a0a3∈E（H），故由引理2知a4∈｛a6－i｜i∈［1，3］｝.因为a1≤3且m≥8，所以a4≥m＋1，并且a1a4、a1a5∈E（H），从而a3a5∉E（H），a3≥m－2.进而a1a3∉E（H）（否则，顶点a0、a3、a1、a4导出一个4－圈），那么a3－a1≤3，故a1≥a3－3≥m－5＝3.由此可得m＝8，a3＝6且a5＝9.从而a0a2、a2a5∈E（H），所以顶点a0、a2、a5、a1、a4导出一个5－圈，矛盾.

2）假设a5＝m＋2.那么a0＝0（否则，若a0＝1，则可以对a0，a1，…，a6通过一个单位“转换”像1）一样得出矛盾）.

2.1）若a4＝m＋1，则由a1≤3可知a1a4∈E（H）.那么a3∈｛a1＋i，a4－i｜i∈［1，3］｝.

当a3∈｛a1＋i｜i∈［1，3］｝时，若a1≥2，则a1a5∈E（H），那么由引理2知a2≥m－2，从而a0a2、a0a3、a1a3∈E（H），且a2＝m－1（否则，顶点a0、a2、a5、a1、a3导出一个5－圈，矛盾），所以顶点a0、a2、a1、a3导出一个4－圈，矛盾.若a1＝1，则a3≤4，故a2a4、a2a5、a3a4、a3a5∈E（H），即a2、a4、a3、a5导出一个4－圈，也推出矛盾.

当a3∈｛a4－i｜i∈［1，3］｝时，即a3≥m－2时，有a0a3、a1a3∈E（H）（若a1a3∉E（H），则a1≥m－5＝3，m＝8，且由引理5可知a6＝m＋4，故顶点a0、a2、a6、a3导出一个4－圈，矛盾）.由引理2知a2≤a1＋3，那么顶点a0、a2、a4、a1、a3导出一个5－圈（若a2∈［4，5］），或者a1、a3、a5、a2、a4导出一个5－圈（若a2＝3），或者a0、a2、a5、a1、a3导出一个5－圈（若a2＝6），也推出矛盾.

2.2）若a4≤m，则a0a4∈E（H），那么由引理2有a3≤3或者a3≥a4－3成立.若a3≤3，则a3＝3且a2＝2，从而a4≤6（否则，顶点a2、a3都和顶点a4、a5相邻，它们导出一个4－圈，矛盾），所以a4a5∈E（H），故由a2a5∈E（H）可知a4∈［4，5］.那么a4a6∈E（H）且a6＝m＋4（否则，a6＝m＋3，顶点a3、a5、a4、a6导出一个4－圈，矛盾）.不失一般性，假设a4＝5.此时H中共有n－1种颜色染m－2个顶点4，6，…，m＋1，m＋3，使得每一种颜色恰染6个满足v5－v0≤7的顶点v0（≥4）、v1、v1＋1、v1＋2、v1＋3、v5，且v1＋3≥9.由引理4～6知，顶点m＋8、m＋9必染α色，但它们与a5、a6一起导出一个4－圈，矛盾.若a3≥a4－3，则a3a4∉E（H），并假设a0a3∈E（H），从而a3≥4.若a3＞a1＋3，则a1a3∈E（H）且顶点a0、a3、a1、a4导出一个4－圈，矛盾.从而a3≤a1＋3≤6，故a2a5、a3a5、a3a6∈E（H），那么由引理2知，a4≤a6－3，即a4＝m，a6＝m＋3，a3≥m－3，a1a4∈E（G），从而a1a5、a1a3∈E（H）（否则，顶点a0、a3、a5、a1、a4导出一个5－圈，或者顶点a0、a3、a1、a4导出一个4－圈）.所以a1＝1，a3＝4，与a3a4∉E（H）矛盾.

总之，可得a5＝m＋3，从而a6＝m＋4.

由a0、a1与a5、a6在H中的对称性可得a0＝0且a1＝1.

子断言2a3＝m＋1且a4＝m＋2.

若a3≤m，则a3＝3或者a0a3∈E（G）.

1）假设a3＝3，则a2＝2，a3a5∈E（G），从而a4∈｛a3＋i，a5－i｜i∈［1，3］｝.当a4∈｛a3＋i｜i∈［1，3］｝时，4≤a4≤6，那么a4a5、a4a6∈E（G）.共有n－1种颜色染［4，a4－1］∪［a4＋1，m＋2］中的m－2个点，由引理4～6知，每一种颜色恰染满足条件v5－v0≤7的6个顶点（4≤）v0、v1、v1＋1、v1＋2、v1＋3、v5（≤m＋2），从而m＋8必染α色，但它与a5、a4、a6导出一个圈，矛盾.

当a4∈｛a5－i｜i∈［1，3］｝且a3a4∈E（G）时，a4a5∉E（G），那么a4≥m.令a4＝m＋i，其中i∈［0，2］.共有n－1种颜色染［4，a4－1］∪［a4＋1，m＋2］中的m－2个点，由引理4～6知，每一种颜色恰染满足条件v5－v0≤7的6个点（4≤）v0、v1、v1＋1、v1＋2、v1＋3、v5（≤m＋2），那么由引理6知，点m＋7必染α色，但它与a4、a3、a5导出一个4－圈，矛盾.

2）假设a0a3∈E（G）.那么m≥a3≥4且a3a6∈E（G），从而有a4∈｛a3＋i｜i∈［1，3］｝或者a4∈｛a6－i｜i∈［1，3］｝.

2.1）若a4∈｛a3＋i｜i∈［1，3］｝，则a3≥m＋2且a4≥m＋1（否则，a4＜m，则a0a4、a4a6∈E（H），那么顶点a0、a3、a6、a4导出一个4－圈，矛盾）.① 假设a4＝m＋1，那么a1a4、a1a3∈E（H）.若a2a3∈E（H），则a2a4∈E（H），故顶点a1、a3、a2、a4导出一个4－圈，矛盾.从而a3－a2≤3且a2≥a3－3≥m－5≥3.若a2＝3，则有m＝8且a3＝6，那么a1a3、a3a5、a2a5、a2a4、a1a4∈E（H），即顶点a1、a3、a5、a2、a4导出一个5－圈，矛盾.所以a2＞3，从而顶点a0、a2、a6、a3导出一个4－圈，也推出矛盾.② 假设a4＝m＋2，那么a3≥m－1，故a1a3∈E（H）.若a2＞4，则顶点a0、a2、a6、a3导出一个4－圈，矛盾.故a2≤3，a2a3、a2a4∈E（G）.令a2＝i，其中i∈［2，3］，a3＝j∈［m－1，m］，那么共有n－1种颜色染H的顶点子集［2，m＋1］＼［i，j］中的m－2个点，使得每一种颜色恰染满足条件v5－v0≤7的6个点（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m＋1）.由引理6知，点m＋6必染α色，但它与a3、a2、a4导出一个4－圈，矛盾.

2.2）若a4∈｛a6－i｜i∈［1，3］｝，假设a3a4∈E（H），那么a4≥m＋1且4≤a3≤a4－4.显然，a2a4、a3a5∈E（G），故a2a3、a2a5∉E（G），那么a2＝2且4≤a3≤5.令a3＝i，其中i∈［4，5］，并令a4＝j，其中j∈［m＋1，m＋2］.共有n－1种颜色染H中m－2个点［3，m＋2］＼｛i，j｝，使得每一种颜色恰染满足条件v5－v0≤7的6个点（3≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m＋2）.从而点m＋7必染α色，但它与a4、a3、a5导出一个圈，矛盾.

综上可得，a3＝m＋1，那么a4＝m＋2.从而断言成立.

若4≤a2≤m－3，则顶点a1、a2、a3导出一个3－圈，矛盾.从而有a2≤4或者a2≥m－2.若a2≤4，则a2a3、a2a4∈E（H）.共有n－1种颜色染H中m－2个点［2，m］＼｛a2｝，由引理4～6知，每一种颜色恰染满足条件v5－v0≤7的6个点（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m），由引理6知，顶点m＋6必染α色，但它与a4、a2、a3导出一个圈，矛盾.若a2≥m－2，则a1a2、a1a3∈E（H）.同样只有n－1种颜色染H中m－2个点［2，m］＼｛a2｝，由引理4～6知，每一种颜色恰染满足条件v5－v0≤7的6个点（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m）.那么顶点m＋5必染α色，但它与a3、a1、a2导出一个4－圈，亦推出矛盾.

［1］ CATLIN P A，LAI H J.Vertex arboricity and maximum degree［J］.Discrete Mathematics，1995，141：37－46.

［2］ ˇSKREKOVSKI R.On the critical point－arboricity graphs［J］.J Graph Theory，2002，39：50－61.

［3］ EGGLETON R B，ERDÖS P，SKILTON D K.Colouring the real line［J］.J Combin Theory：Ser B，1985，39：86－100.

［4］ CHANG G J，LIU D F，ZHU X D.Distance graphs and T－coloring［J］.J Combin Theory：Ser B，1999，75：259－269.

［5］ YU Q L，ZUO L C.The fractional vertex arboricity of graphs［J］.Lecture Notes in Computer Science，2007（1）：245－252.

［6］ ZUO L C，YU Q，WU J L.Vertex aboricity of integer distance graphG（Dm，k）［J］.Discrete Mathematics，2009，309：1649－1657.

Vertex arboricity of a class of integer distance graphs

XULi，ZUOLian－cui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

An integer distance graph is a graph with all integers as vertex set，and two verticesu，v∈Zare adjacent if and only if－v∈Dwhere the distance setDis a subset of the positive integer set.LetDm＝［1，m］＼［1，3］form＞3，the vertex arboricity of the integer distance graphG（Dm）is obtained.

integer distance graph；vertex arboricity；tree coloring；proper coloring；chromatic number

O157.5

A

1671－1114（2012）03－0013－05

2011－11－15

天津师范大学引进人才科研启动基金资助项目（5RL066）

徐 莉（1988—），女，硕士研究生.

左连翠（1964—），女，教授，主要从事图论及其应用方面的研究.

（责任编校 马新光）