|
|
|
| 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 |
|
|
|
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.
|
|
Received: 26 December 2016
Published: 01 May 2017
|
|
|
| Fund: 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). |
Cartesian积与邻点可区别着色之间的关系
图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积,
正常边染色,
正常全染色,
邻点可区别边染色,
邻点可区别全染色
|
|
[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. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
