Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. (English) Zbl 1517.05060
Chen, Jianer (ed.) et al., Theory and applications of models of computation. 16th international conference, TAMC 2020, Changsha, China, October 18–20, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12337, 426-438 (2020).
Summary: An acyclic edge coloring of a graph \(G\) is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by I. Fiamcik [Math. Slovaca 28, 139–145 (1978; Zbl 0388.05015)] and N. Alon et al. [J. Graph Theory 37, No. 3, 157–167 (2001; Zbl 0996.05050)] states that every simple graph with maximum degree \(\varDelta\) is acyclically edge \((\varDelta + 2)\)-colorable. Despite many milestones, the conjecture is still unknown true or not even for planar graphs. In this paper, we first show by discharging methods that every planar graph without intersecting triangles must have one of the six specified groups of local structures; then by induction on the number of edges we confirm affirmatively the conjecture on planar graphs without intersecting triangles.
For the entire collection see [Zbl 1502.68022].
For the entire collection see [Zbl 1502.68022].
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Alon, N.; Mcdiarmid, C.; Reed, B., Acyclic coloring of graphs, Random Struct. Algorithms, 2, 277-288 (1991) · Zbl 0735.05036 · doi:10.1002/rsa.3240020303 |
| [2] | Alon, N.; Sudakov, B.; Zaks, A., Acyclic edge colorings of graphs, J. Graph Theory, 37, 157-167 (2001) · Zbl 0996.05050 · doi:10.1002/jgt.1010 |
| [3] | Andersen, LD; Máčajová, E.; Mazák, J., Optimal acyclic edge-coloring of cubic graphs, J. Graph Theory, 71, 353-364 (2012) · Zbl 1292.05105 · doi:10.1002/jgt.20650 |
| [4] | Basavaraju, M.; Chandran, LS, Acyclic edge coloring of graphs with maximum degree \(4\), J. Graph Theory, 61, 192-209 (2009) · Zbl 1221.05127 · doi:10.1002/jgt.20376 |
| [5] | Basavaraju, M.; Chandran, LS; Cohen, N.; Havet, F.; Müller, T., Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math., 25, 463-478 (2011) · Zbl 1294.05070 · doi:10.1137/090776676 |
| [6] | Esperet, L.; Parreau, A., Acyclic edge-coloring using entropy compression, Eur. J. Comb., 34, 1019-1027 (2013) · Zbl 1285.05056 · doi:10.1016/j.ejc.2013.02.007 |
| [7] | Fiamcik, J., The acyclic chromatic class of a graph, Math. Slovaca, 28, 139-145 (1978) · Zbl 0388.05015 |
| [8] | Giotis, I.; Kirousis, L.; Psaromiligkos, KI; Thilikos, DM, Acyclic edge coloring through the Lovász local lemma, Theoret. Comput. Sci., 665, 40-50 (2017) · Zbl 1357.05042 · doi:10.1016/j.tcs.2016.12.011 |
| [9] | Hou, J.; Roussel, N.; Wu, J., Acyclic chromatic index of planar graphs with triangles, Inf. Process. Lett., 111, 836-840 (2011) · Zbl 1260.05161 · doi:10.1016/j.ipl.2011.05.023 |
| [10] | Molloy, M., Reed, B.: Further algorithmic aspects of the local lemma (1998) · Zbl 1028.68105 |
| [11] | Ndreca, S.; Procacci, A.; Scoppola, B., Improved bounds on coloring of graphs, Eur. J. Comb., 33, 592-609 (2012) · Zbl 1244.05094 · doi:10.1016/j.ejc.2011.12.002 |
| [12] | Shu, Q., Chen, Y., Han, S., Lin, G., Miyano, E., Zhang, A.: Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. arXiv (2020) · Zbl 1517.05060 |
| [13] | Shu, Q.; Wang, W.; Wang, Y., Acyclic edge coloring of planar graphs without \(5\)-cycles, Discrete Appl. Math., 160, 1211-1223 (2012) · Zbl 1242.05103 · doi:10.1016/j.dam.2011.12.016 |
| [14] | Shu, Q.; Wang, W.; Wang, Y., Acyclic chromatic indices of planar graphs with girth at least \(4\), J. Graph Theory, 73, 386-399 (2013) · Zbl 1269.05041 · doi:10.1002/jgt.21683 |
| [15] | Shu, Q.; Wang, Y.; Ma, Y.; Wang, W., Acyclic edge coloring of \(4\)-regular graphs without 3-cycles, Bull. Malays. Math. Sci. Soc., 42, 285-296 (2019) · Zbl 1406.05040 · doi:10.1007/s40840-017-0484-x |
| [16] | Vizing, VG, On an estimate of the chromatic class of a \(p\)-graph, Discret Analiz, 3, 25-30 (1964) · Zbl 1539.05042 |
| [17] | Wang, T.; Zhang, Y., Acyclic edge coloring of graphs, Discrete Appl. Math., 167, 290-303 (2014) · Zbl 1284.05110 · doi:10.1016/j.dam.2013.12.001 |
| [18] | Wang, T.; Zhang, Y., Further result on acyclic chromatic index of planar graphs, Discrete Appl. Math., 201, 228-247 (2016) · Zbl 1329.05121 · doi:10.1016/j.dam.2015.07.015 |
| [19] | Wang, W.; Ma, Y.; Shu, Q.; Wang, Y., Acyclic edge coloring of \(4\)-regular graphs (II), Bull. Malays. Math. Sci. Soc., 42, 2047-2054 (2019) · Zbl 1419.05085 · doi:10.1007/s40840-017-0592-7 |
| [20] | Wang, W.; Shu, Q.; Wang, Y., Acyclic edge coloring of planar graphs without \(4\)-cycles, J. Comb. Optim., 25, 562-586 (2013) · Zbl 1294.90067 · doi:10.1007/s10878-012-9474-y |
| [21] | Wang, W.; Shu, Q.; Wang, Y., A new upper bound on the acyclic chromatic indices of planar graphs, Eur. J. Comb., 34, 338-354 (2013) · Zbl 1254.05059 · doi:10.1016/j.ejc.2012.07.008 |
| [22] | Wang, Y.; Shu, Q.; Wu, J-L; Zhang, W., Acyclic edge coloring of planar graphs without a \(3\)-cycle adjacent to a \(6\)-cycle, J. Comb. Optim., 28, 3, 692-715 (2014) · Zbl 1337.90076 · doi:10.1007/s10878-014-9765-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
