《k2n的rr11染色》由会员分享，可在线阅读，更多相关《k2n的rr11染色（28页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学 硕士学位论文 K的r，r+1，1-染色 姓名：李红菊 申请学位级别：硕士 专业：应用数学 指导教师：徐常青 20091201 ? K2n?r,r + 1,1-? ? ?G = (V(G),E(G)?r, s, t,?G ?r, s,t-?V(G) E(G)?0,1,.,k 1?c,? ?vi,vj,?|c(vi) c(vj)| r;? ei,ej,?|c(ei) c(ej)| s;?vi V(G), ej E(G), ?|c(vi) c(ej)| t.?G?r, s,t-?k?G? r, s,t-?r,s,t(G).?K2n?r,r + 1,1-? ?2,3,1(K2n) = 6
2、n 4?n 3.?r 3? ?(a)?r 2n,?r,r+1,1(K2n) = r(2n 1) + 1; (b)?r 2n,? (r +1)(2n 2)+2 r,r+1,1(K2n) (r +1)(2n 2)+3; (c)?r 3?r n1, ?r,r+1,1(K2n) = (r + 1)(2n 2) + 2. ?r, s,t-? i K2n?r,r + 1,1-? r,r + 1,1-COLORING OF K2n ABSTRACT Let G = (V(G),E(G) be a simple graph. Given non-negative integers r, s, and t, a
3、n r, s,t-coloring of G is a mapping c from V(G) S E(G) to the color set 0,1,.,k 1 such that |c(vi) c(vj)| r for every two adjacent vertices vi, vj, |c(ei) c(ej)| s for every two adjacent edges ei, ej, and |c(vi) c(ej)| t for all pairs of incident vertices and edges, respectively. Ther, s,t-chromatic
4、 number r,s,t (G)ofG is defi ned to be the minimum k such thatG admits an r, s,t- coloring. We get that 2,3,1(K2n) = 6n 4 for n 3. and for general condition r 3, we get that (a) r,r+1,1(K2n) = r(2n1)+1, if r 2n; (b) (r+1)(2n2)+2 r,r+1,1(K2n) (r+1)(2n2)+3, if r 2n; (c) r,r+1,1(K2n) = (r+1)(2n2)+2, if
5、 r 3 and r n 1. KEY WORDS: coloring, complete graph, r, s,t-coloring ii K2n?r,r + 1,1-? ? 1. K2n?2n? 2. (G)?G? 3. V(G)?G? 4. Kn,n? 5. (G)?G? 6. E(G)?G? 7. V(G) S E(G)?G? 8. (G)?G? 9. C = 0,1,.,k 1?k? 10. (G)?G? 11. r,s,t(G)?G?r, s,t-? 12. (G)?G? 13. (G)?G? 14. (G)?G? 15. T d(G)G ?(d,1)-? iv ? ? ? ?
6、? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 200? 1-1? ?18 ? ? ? ? ? ?7? ? ?(Euler L)? ? ? ? ? ? ? (Graph Theory).? ? ? ? ?(?1-3). 1 K2n?r,r + 1,1-? 1750?(Goldbach C)? ?n,?e,?f,?n e + f = 2.? ? ?19? ?(?4).? ?n,?e,?f?ne+ f = 2,? ?(?5).? ? ?19? ? ? ? ? ? ? ? ? ? ? ? ?88? ?64? ?64? ? ?64 ? ? ? ? ? ? ?1757? ?1759? ?1771? ? ? ?60-80? ? ? ? 2 ? ? ? ? ? ? ?(?6-7). 1-2? ?n?G,? ? ?G? ? ?(?8)?T-?(?9)?(? 9)?(?9)?(?9-11)? ? ? ?n? ? ?v1,v2,.,vn?n?vi,vj? ?vi,vj? ?
