一种新的色对策和对策染色数.pdf

第 “卷 第期中国矿业大学学报 6设 是正实数记号 表示不小于的最小整数 表示不大于的 一个映射 对任意A / 0 如果A / B 则 ’ A C ’ 6为了讨论方便在4的色对策D的过程 中若顶点./ 0 被分配的颜色是E 则仍记作 ’ . U’ 4 U’ 4H H U’ 4H H U’ 4 M Y 我们只需给出4的一个 使得F利用Y种颜色的获胜策略即可6最初 F可 以选取任意顶点作为G步点在J对图进行着色 色不妨假设J选取了4 H中的顶点 接下来F进行 着色时 F不首先引进新色’除非为了保证正常着 色 首先考虑在J刚刚着色的子图中选取顶点进 行着色即F与J在同一个子图中进行着色若F 不能与J在同一个子图中进行着色时再考虑在其 它的子图中进行着色6这样由4 HR 4I U’ 4 3 Y 结果 成立6 引理[ \ 设4 U’ 4 U’ 4 U’ 4 U’ b U’ Kd U’ K 7 d U’ Kd U’ K 7 d U’ 4 7 U’ 89’ b U’ 4 U’ rN q U’ rd 其内点. 0 . .,皆未着色则.可以着色/ 矛盾2由于-为 圈所以各个/色区间相互独立我们考虑一个/ 色区间2由于任意/色区间的长度7 /8 每个/ 色区间至多包含两个内点引进两种新颜色即可完 成色对策 9/ ./ .,; 这样必须引进两种新色才可使. 0 .着色所以 中必有一点S有 S* “ / 否则P可着色/ 且OT G P H仍是K的一个极大独立集与O的极大 性 矛盾U注意到K的最大度是, 且只有各个圈上 的公共点是,度点其他顶点均是0度点所以K中 尚未着色的顶点集合的导出子图K Q V O *的各个 连通分支或是孤立点或是0或是/ 0或是/ 由引理/和0知它们至多需要两种新色从而 W X Y Z [ \ ] Y \ _ ‘ a ]b c \d X ef Z \ g h b iX j k X e\d X Z X h ] l l [ e\ m; h ] Ln X d \ \ Y h ] l kX jopoX q k c X fX ] p [ f cr c \ X \ b h d [ Z s X ] d \ f b k h ]s X ef t b \ u d h \ ] d \ s ; / v v I 5 C v 0 ; w [ h l Z \xy\ ]oyh \ k b \ [ Y h _ m\ b[ Z a ]b c \ l [ e\d c X e[ b h d] t ez \ kX jk X e\d Z [ k k \ kX jl [ f c k { ; m k s X ez h ] / v v 5 * L / , C / 5 I ; s c \ ]pu d c \ Z f|_u c \ } \ o m] \ l [ e\ d c X C e[ b h d] t ez \ { ; {s X ez h ] / v v “ / * L / C v , ; W X ] Y i{ mt b ix u| p [ f cb c \ X ih b c[ f f Z h d [ C b h X ] ; / v “ / C I \ p [ e\s c X e[ b h d [ ] Yp [ e\s c X e[ b h d t ez \ ’ po\ h /‘ ’ x h C q t h0 / \ f [ b e\ ] b X j [ b c X j r [ h [ ]r \ [ d c \ k s X Z Z \ l \ r [ h [ ] u c [ ] Y X ] l0 “ / I / v s c h ] [ B 0 r \ d c ] X Z X l i Y t d [ b h X ]s X Z Z \ l \X j t * c X tX e[ Z x] h } \ k h b i t * c X t { h [ ] l k t0 0 / I / / s c h ] [* , - . / 0 1 . Lr c h k f [ f \ h ] b X Y t d \ k [] \ l [ e\d c X e[ b h d[ ] Yl [ e\d c X e[ b h d] t ez \ W iZ [ z \ Z h ] lb c \} \ b \ g X j l [ f ch b cd X Z X b c h k f [ f \ Y \ b \ eh ] \ k b c \d c X e[ b h d ] t ez \ X j d i d Z \[ ] YX b c \ l [ f c k m] Y[ Z k XY \ b \ C eh ] \ k b c \f X f \ b iX j b c \l [ e\d c X e[ b h d] t ez \ 23 45 6 / 7 - L} \ b \ gd X Z X h ] l Bl [ e\d c X e[ b h d Bl [ e\d c X e[ b h d] t ez \ ,00 中国矿业大学学报第0 v卷 万方数据