The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle

Discrete Applied Mathematics - Tập 161 - Trang 2687-2694 - 2013
Yiqiao Wang1, Qiaojun Shu2, Weifan Wang2
1School of Management, Beijing University of Chinese Medicine, Beijing 100029, China
2Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China

Tài liệu tham khảo

Alon, 1991, Acyclic coloring of graphs, Random Structures Algorithms, 2, 277, 10.1002/rsa.3240020303 Alon, 2001, Acyclic edge colorings of graphs, J. Graph Theory, 37, 157, 10.1002/jgt.1010 Basavaraju, 2008, Acyclic edge coloring of subcubic graphs, Discrete Math., 308, 6650, 10.1016/j.disc.2007.12.036 Basavaraju, 2009, Acyclic edge coloring of graphs with maximum degree 4, J. Graph Theory, 61, 192, 10.1002/jgt.20376 Basavaraju, 2011, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math., 25, 463, 10.1137/090776676 L. Esperet, A. Parreau, Acyclic edge-coloring using entropy compression, http://arxiv.org/abs/1206.1535v1. Fiamčik, 1978, The acyclic chromatic class of a graph, Math. Slovaca, 28, 139 Fiedorowicz, 2012, Acyclic edge colouring of plane graphs, Discrete Appl. Math., 160, 1513, 10.1016/j.dam.2012.02.018 M. Molloy, B. Reed, Further algorithmic aspects of Lovász local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524–529. Ndreca, 2012, Improved bounds on coloring of graphs, European J. Combin., 33, 592, 10.1016/j.ejc.2011.12.002 Shu, 2013, Acyclic chromatic indices of planar graphs with girth at least four, J. Graph Theory, 73, 386, 10.1002/jgt.21683 Shu, 2012, Acyclic edge coloring of planar graphs without 5-cycles, Discrete Appl. Math., 160, 1211, 10.1016/j.dam.2011.12.016 Skulrattanakulchai, 2004, Acyclic colorings of subcubic graphs, Inform. Process. Lett., 92, 161, 10.1016/j.ipl.2004.08.002 Vizing, 1964, On an estimate of the chromatic index of a p-graph, Diskret. Anal., 3, 25 Wang, 2012, Acyclic edge coloring of sparse graphs, Discrete Math., 312, 3561, 10.1016/j.disc.2012.08.012 Wang, 2013, A new upper bound on the acyclic chromatic indices of planar graphs, European J. Combin., 34, 338, 10.1016/j.ejc.2012.07.008 Wang, 2013, Acyclic edge coloring of planar graphs without 4-cycles, J. Comb. Optim., 25, 562, 10.1007/s10878-012-9474-y W. Wang, Q. Shu, Y. Wang, Every 4-regular graph is acyclically edge-6-colorable, http://arxiv.org/abs/1209.2471v1.