Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2017, Vol. 44 Issue (5): 520-525    DOI: 10.3785/j.issn.1008-9497.2017.05.004
数学与计算机科学     
Cartesian积与邻点可区别着色之间的关系
王国兴1,2
1. 兰州财经大学 甘肃商务发展研究中心, 甘肃 兰州 730020;
2. 兰州财经大学 信息工程学院, 甘肃 兰州 730020
Relation between Cartesian product and adjacent vertex distinguishing coloring
WANG Guoxing1,2
1. Gansu Business Development Research Center, Lanzhou University of Finance and Economics, Lanzhou 730020, China;
2. College of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China
 全文: PDF(899 KB)   HTML  
摘要： 图G的一个正常k-边着色是指k种颜色1，2，…，k对图G各边的一个分配，使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x，Sf（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v，有S（u）≠S（v），则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数，称为G的邻点可区别正常边色数，记为χ'a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配，使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x，使用Cg（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v，有C（u）≠C（v），则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数，记为χ″a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.
关键词： Cartesian积;  正常边染色;  正常全染色;  邻点可区别边染色;  邻点可区别全染色    
Abstract: A proper k-edge coloring of a graph G is an assignment of k colors 1,2,…,k to edges of G such that any two adjacent edges receive the different colors. For a proper edge coloring f of G and any vertex x of G, we use Sf(x) or S(x) to denote the set of the colors assigned to the edges incident with x. If for any two adjacent vertices u and v of G, we have S(u)≠S(v), then f is called the adjacent vertex distinguishing proper edge coloring of G (or AVDPEC of G in brief). The minimum number of colors required in an AVDPEC of G is called the adjacent vertex distinguishing proper edge chromatic number of G, denoted by χ'a(G). A proper k-total coloring of a graph G is an assignment of k colors 1,2,…,k to vertices and edges of G such that any two adjacent or incident elements receive the different colors. For a proper total coloring g of G and any vertex x of G, we use Cg(x) or C(x) to denote the set of the colors assigned to the vertex x and edges incident with x. If for any two adjacent vertices u and v of G, we have C(u)≠C(v), then g is called the adjacent vertex distinguishing total coloring of G (or AVDTC of G in brief). The minimum number of colors required in an AVDTC of G is called the adjacent vertex distinguishing total chromatic number of G, denoted by χ″a(G). In this paper, we discuss the relation between Cartesian product and two types of adjacent vertex distinguishing coloring.
Key words: Cartesian product    proper edge coloring    proper total coloring    adjacent vertex distinguishing proper edge coloring    adjacent vertex distinguishing total coloring
收稿日期: 2016-12-26 出版日期: 2017-05-01
CLC:  O157.5  
基金资助: Supported by the National Natural Science Foundation of China (61662066),Gansu Business Development Research Center Project of Lanzhou University of Finance and Economics (JYYY201506) and Key Science and Research Project of Lanzhou University of Finance and Economics (LZ201302).
作者简介: 王国兴(1976-),ORCID:http://orcid.org/0000-0001-6582-650X,male,master,associate professor,the field of interest are the graph theory and its applications,E-mail:wanggx@lzufe.edu.cn.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
王国兴

引用本文:

王国兴. Cartesian积与邻点可区别着色之间的关系[J]. 浙江大学学报（理学版）, 2017, 44(5): 520-525.

WANG Guoxing. Relation between Cartesian product and adjacent vertex distinguishing coloring. Journal of Zhejiang University (Science Edition), 2017, 44(5): 520-525.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2017.05.004    或    https://www.zjujournals.com/sci/CN/Y2017/V44/I5/520

[1] BALISTER P N, GYÖRI E, LEHEL J, et al. Adjacent vertex distinguishing edge-colorings[J]. SIAM J Discrete Math,2007,21(1):237-250.
[2] BARIL J L, KHEDDOUCI H, TOGNI O. Adjacent vertex distinguishing edge colorings of meshes[J]. Australasian Journal of Combinatorics,2006,35:89-102.
[3] GREENHILL C, RUCIИSKI A. Neighbour distinguishing edge colorings of random regular graphs[J]. The Electronic Journal of Combinatorics,2006,13(#R77):1-12.
[4] HATAMI H. Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. Journal of Combinatorial Theory:Series B,2005,95:246-256.
[5] EDWARDS K, HOR AЙÁK M, WO A?G NIAK M. On the neighbour distinguishing index of a graph[J]. Graphs and Combinatorics,2006,22:341-350.
[6] ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Appl Math Lett,2002,15:623-626.
[7] ZANG Z F, CHEN X E, LI J W, et al. On adjacent vertex distinguishing total coloring of graphs[J]. Science in China (Ser A):Mathematics,2005,48(3):289-299.
[8] CHEN X E. Adjacent-vertex-distinguishing total chromatic numbers on K2n+1-E(P3)[J]. International Journal of Pure and Applied Mathematics,2004,13(1):21-29.
[9] CHEN X E. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ=3[J]. Discrete Mathematics,2008,308:4003-4007.
[10] CHEN X E, ZHANG Z F. AVDTC numbers of generalized Halin graphs with maximum degree at least 6[J]. Acta Mathematicae Applicatae Sinica:English Series,2008,24(1):55-58.
[11] CHEN X E, ZHANG Z F. Adjacent-vertex-distinguishing total chromatic numbers of Pm×Kn[J]. J Mathematical Research and Exposition,2006,26(3):489-494.
[12] CHEN X E, ZHANG Z F, SUN Y R. Adjacent-vertex-distinguishing total chromatic numbers on monocycle graphs and the square of cycles[J]. International Journal of Pure and Applied Mathematics,2005,18(4):481-491.
[13] CHEN X E, ZHANG Z F, SUN Y R. A note on adjacent-vertex-distinguishing total chromatic numbers for Pm×Pn,Pm×Cn and Cm×Cn[J]. J Mathematical Research and Exposition,2008,28(4):789-798.
[14] HULGAN J. Concise proofs for adjacent vertex distinguishing total colorings[J]. Discrete Mathematics,2009,309:2548-2550.
[15] SUN Y L, SUN L. The (adjacent) vertex-distinguishing total coloring of the Mycielski graphs and the Cartesian product graphs[C]//7-th China-Japan Conference, Discrete Geometry, Combinatorics and Graph Theory. Heidelberg:Springer-Verlag,2007:200-205.
[16] WANG H Y. On the adjacent vertex distinguishing total chromatic numbers of graphs with Δ=3[J]. J Comb Optim,2007,14:87-109.
[17] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York:Elsevier Science Publishing Co. Inc.,1976.
[18] TONG C L, LIN X H, YANG Y S, et al. Equitable total coloring of CmCn[J]. Discrete Applied Mathematics,2009,157:596-601.
[1] 杜娟, 吕大梅, 张科. Cartesian积的局部边-路替换图的L(2,1)-标号[J]. 浙江大学学报（理学版）, 2016, 43(6): 679-681.