On acyclic edge-coloring of the complete bipartite graphs K 2 p - 1 , 2 p - 1 for odd prime p
作者： Ayineedi Venkateswarlu , Santanu Sarkar
DOI: 10.1016/J.DISC.2015.07.010
关键词: Graph 、 Edge coloring 、 Vertex (geometry) 、 Bipartite graph 、 Discrete mathematics 、 Combinatorics 、 Mathematics 、 Complete bipartite graph
摘要: An acyclic edge-coloring of a graph is proper without bichromatic (2-colored) cycles. The chromatic index G , denoted by ' ( ) the least integer k such that admits an using colors. Let Δ = denote maximum degree vertex in . A complete bipartite with n vertices on each side K Basavaraju, Chandran and Kummini proved ? + 2 when odd. Basavaraju showed p which implies odd prime, main tool their proof perfect 1-factorization In this paper we study case - 1 also possess 1-factorization, where prime. We show colors so get
acm.org
elsevier.com
sci-hub.se 参考文章(13)
Weifan Wang, Yuehua Bu, On Coloring Problems Springer, New York, NY. pp. 2095- 2189 ,(2013) , 10.1007/978-1-4419-7997-1_59
Rahul Muthu, N. Narayanan, C. R. Subramanian, Optimal acyclic edge colouring of grid like graphs computing and combinatorics conference. pp. 360- 367 ,(2006) , 10.1007/11809678_38
Sokol Ndreca, Aldo Procacci, Benedetto Scoppola, Improved bounds on coloring of graphs The Journal of Combinatorics. ,vol. 33, pp. 592- 609 ,(2012) , 10.1016/J.EJC.2011.12.002
Jaroslav Nešetřil, Nicholas C. Wormald, The acyclic edge chromatic number of a random d-regular graph is d + 1 Journal of Graph Theory. ,vol. 49, pp. 69- 74 ,(2005) , 10.1002/JGT.V49:1
Midori Kobayashi, On perfect one-factorization of the complete graph K 2 p . Graphs and Combinatorics. ,vol. 5, pp. 351- 353 ,(1989) , 10.1007/BF01788690
Ayal Zaks, Benny Sudakov, Noga Alon, Acyclic edge colorings of graphs Journal of Graph Theory. ,vol. 37, pp. 157- 167 ,(2001) , 10.1002/JGT.V37:3
Manu Basavaraju, L. Sunil Chandran, A note on acyclic edge coloring of complete bipartite graphs Discrete Mathematics. ,vol. 309, pp. 4646- 4648 ,(2009) , 10.1016/J.DISC.2009.01.014
Rahul Muthu, N. Narayanan, C. R. Subramanian, Acyclic Edge Colouring of Outerplanar Graphs algorithmic applications in management. pp. 144- 152 ,(2007) , 10.1007/978-3-540-72870-2_14
Branko Grünbaum, Acyclic Colorings of Planar Graphs. Israel Journal of Mathematics. ,vol. 14, pp. 390- 408 ,(1973) , 10.1007/BF02764716
Manoj Kummini, Manu Basavaraju, L. Sunil Chandran, d-Regular graphs of acyclic chromatic index at least d+2 Journal of Graph Theory. ,vol. 63, pp. 226- 230 ,(2010) , 10.1002/JGT.V63:3