Recent progress on strong edge-coloring of graphs. (English) Zbl 1426.05040
Summary: A strong edge-coloring of a graph \(G = (V, E)\) is a partition of its edge set \(E\) into induced matchings. In this paper, we gave a short survey on recent results about strong edge-coloring of a graph.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Math.108 (1992) 231-252. · Zbl 0756.05050 |
| [2] | W. C. V. Batenburg and R. J. Kang, Squared chromatic number without claws or large cliques, preprint (2016), arXiv:1609.08646v2 [math.CO]. · Zbl 1409.05082 |
| [3] | Bensmail, J., Bonamy, M. and Hocquard, H., Strong edge-coloring sparse graphs, Electron. Notes Discrete Math.49 (2015) 773-778. · Zbl 1346.05058 |
| [4] | Bensmail, J., Haratyunyan, A., Hocquard, H. and Valicov, P., Strong edge-coloring of sparse planar graphs, Discrete Appl. Math.179 (2014) 229-234. · Zbl 1303.05057 |
| [5] | Bensmail, J., Lagoutte, A. and Valicov, P., Strong edge-coloring of \((3, \Delta)\)-bipartite graphs, Discrete Math.339 (2016) 391-398. · Zbl 1322.05055 |
| [6] | M. Bonamy, T. Perrett and L. Postle, Coloring graphs with sparse neighborhood: Bounds and application, preprint (2016), arXiv:1810.06704 [math.CO]. · Zbl 1492.05041 |
| [7] | Borodin, O. V. and Ivanova, A. O., Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory33 (2013) 759-770. · Zbl 1301.05118 |
| [8] | Brandstädt, A., Eschen, E. and Sritharan, R., The induced matching and chain subgraph cover problems for convex bipartite graphs, Theoret. Comput. Sci.381 (2007) 260-265. · Zbl 1188.68209 |
| [9] | Brandstädt, A. and Hoàng, C. T., Maximum induced matchings for chordal graphs in linear time, Algorithmica52 (2008) 440-447. · Zbl 1171.68595 |
| [10] | Brualdi, A. T. and Massey, J. J. Quinn, Incidence and strong edge-colorings of graphs, Discrete Math.122 (1993) 51-58. · Zbl 0790.05026 |
| [11] | Bruhn, H. and Joos, F., A stronger bound for the strong chromatic index, Electron. Notes Discrete Math.49 (2015) 277-284. · Zbl 1346.05061 |
| [12] | Cameron, K., Induced matchings, Discrete Appl. Math.24 (1989) 97-102. · Zbl 0687.05033 |
| [13] | Cameron, K., Induced matchings in intersection graphs, Discrete Math.278 (2004) 1-9. · Zbl 1033.05080 |
| [14] | Cameron, K., Sritharan, R. and Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Math.266 (2003) 133-142. · Zbl 1022.05064 |
| [15] | Chang, J.-M., Induced matchings in asteroidal triple-free graphs, Discrete Appl. Math.132 (2003) 67-78. · Zbl 1029.05120 |
| [16] | Chang, G. J., Chen, S. H., Hsu, C. Y., Hung, C. M. and Lai, H. L., Strong edge-coloring for jellyfish graphs, Discrete Math.338 (2015) 2348-2355. · Zbl 1318.05025 |
| [17] | Chang, G. J. and Duh, G. H., On the precise value of the strong chromatic index of a planar graph with a large girth, Discrete Appl. Math.247 (2018) 389-397. · Zbl 1394.05031 |
| [18] | Chang, G. J., Montassier, M., Pêcher, A. and Raspaud, A., Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory34 (2014) 723-733. · Zbl 1303.05063 |
| [19] | Chang, G. J. and Narayanan, N., Strong chromatic index of 2-degenerate graphs, J. Graph Theory73 (2013) 119-126. · Zbl 1264.05047 |
| [20] | Chen, L., Deng, K., Yu, G. and Zhou, X., Strong edge-coloring for planar graphs with large girth, Discrete Math.342(2) (2019) 339-343. · Zbl 1400.05081 |
| [21] | Choi, I., Kim, J., Kostochka, A. V. and Raspaud, A., Strong edge-coloring of sparse graphs with large maximum degree, European J. Combina.67 (2016) 21-39. · Zbl 1371.05076 |
| [22] | Chung, F. R. K., Gyárfás, A., Tuza, Z. and Trotter, W. T., The maximum number of edges in 2K2-free graphs of bounded degree, Discrete Math.81 (1990) 129-135. · Zbl 0698.05039 |
| [23] | Cranston, D., Strong edge-coloring of graphs with maximum degree 4 using 22 colors, Discrete Math.306 (2006) 2772-2778. · Zbl 1143.05025 |
| [24] | Dai, T., Wang, G., Yang, D. and Yu, G., Strong list-chromatic index of subcubic graphs, Discrete Math.341 (2018) 3434-3440. · Zbl 1397.05062 |
| [25] | Dȩbski, M., On a topological relaxation of a conjecture of Erdős and Nešetřil, European J. Combin.49 (2015) 188-193. · Zbl 1315.05050 |
| [26] | Dȩbski, M., Fractional strong chromatic index of bipartite graphs, Discrete Math.340(7) (2017) 1508-1513. · Zbl 1361.05045 |
| [27] | Dȩbski, M., Grytczuk, J. and Śleszyńska-Nowak, M., The strong chromatic index of sparse graphs, Inf. Process. Lett.115(2) (2015) 326-330. · Zbl 1304.05043 |
| [28] | DeOrsey, P., Ferrara, M., Graber, N., Hartke, S. G., Nelsen, L. L., Sullivan, E., Jahanbekam, S., Lidicky, B., Stolee, D. and White, J., On the strong chromatic index of sparse graphs, Electron. J. Combin.25(3) (2018) P3.18. · Zbl 1393.05112 |
| [29] | Duckworth, W., Manlove, D. F. and Zito, M., On the approximability of the maximum induced matching problem, J. Discrete Algorithms3(1) (2005) 79-91. · Zbl 1075.68063 |
| [30] | Erdős, P. and Nešetřil, J., Irregularities of Partitions, eds. Halasz, G., Sòs, V. T. (Springer, Berlin, 1989), pp. 162-163. |
| [31] | Faron, M. and Postle, L., On the clique number of the square of a line graph and its relation to maximum degree of the line graph, J. Graph Theory92 (2019) 261-274. · Zbl 1429.05179 |
| [32] | Faudree, R. J., Gyárfás, A., Schelp, R. H. and Tuza, Zs., The strong chromatic index of graphs, Ars Combin.29B (1990) 205-211. · Zbl 0721.05018 |
| [33] | Fouquet, J. L. and Jolivet, J. L., Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin.16A (1983) 141-150. · Zbl 0536.05027 |
| [34] | Frieze, A., Krivelevich, M. and Sudakov, B., The strong chromatic index of random graphs, SIAM J. Discrete Math.19 (2005) 719-727. · Zbl 1093.05064 |
| [35] | Golumbic, M. C. and Laskar, R. C., Irredundancy in circular arc graphs, Discrete Appl. Math.44 (1993) 79-89. · Zbl 0783.05059 |
| [36] | Golumbic, M. C. and Lewenstein, M., New results on induced matchings, Discrete Appl. Math.101 (2000) 157-165. · Zbl 0951.68104 |
| [37] | Guiduli, B., On incidence coloring and star arboricity of graphs, Discrete Math.163 (1997) 275-278. · Zbl 0871.05022 |
| [38] | Hocquard, H., Montassier, M., Raspaud, A. and Valicov, P., On strong edge-coloring of subcubic graphs, Discrete Appl. Math.161 (2013) 2467-2479. · Zbl 1285.05060 |
| [39] | Hocquard, H. and Valicov, P., Strong edge coloring of subcubic graphs, Discrete Appl. Math.159 (2011) 1650-1657. · Zbl 1228.05152 |
| [40] | Horák, P., The strong chromatic index of graphs with maximum degree four, Contemp. Methods Graph Theory (1990) 399-403. · Zbl 0715.05023 |
| [41] | Horák, P., He, Q. and Trotter, W. T., Induced matchings in cubic graphs, J. Graph Theory17 (1993) 151-160. · Zbl 0787.05038 |
| [42] | Huang, M., Santana, M. and Yu, G., Strong chromatic index of graphs with maximum degree four, Electron. J. Combin.25(3) (2018) P3.31. · Zbl 1395.05057 |
| [43] | Huang, M., Yu, G. and Zhou, X., The strong chromatic index of \((3, \Delta)\)-bipartite graphs, Discrete Math.340 (2017) 1143-1149. · Zbl 1357.05043 |
| [44] | Hudák, D., Luz̆ar, B., Soták, R. and S̆krekovski, R., Strong edge-coloring of planar graphs, Discrete Math.324 (2014) 41-49. · Zbl 1284.05101 |
| [45] | Joos, F., Induced matchings in graphs of bounded maximum degree, SIAM J. Discrete Math.30(3) (2016) 1876-1882. · Zbl 1346.05234 |
| [46] | Joos, F. and Nguyen, V. H., Induced matchings in graphs of degree at most 4, SIAM J. Discrete Math.30(1) (2014) 154-165. · Zbl 1329.05245 |
| [47] | Joos, F., Rautenbach, D. and Sasse, T., Induced matchings in subcubic graphs, SIAM J. Discrete Math.28 (2014) 468-473. · Zbl 1293.05295 |
| [48] | Kobler, D. and Rotics, U., Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica37 (2003) 327-346. · Zbl 1082.68592 |
| [49] | Kostochka, A. V., Li, X., Ruksasakchai, W., Santana, M., Wang, T. and Yu, G., Strong chromatic index of subcubic planar multigraphs, European J. Combin.51 (2016) 380-397. · Zbl 1321.05123 |
| [50] | Lozin, V. V., On maximum induced matchings in bipartite graphs, Inf. Process. Lett.81 (2002) 7-11. · Zbl 1046.68081 |
| [51] | Lv, J., Li, X. and Yu, G., On strong edge-coloring of graphs with maximum degree 4, Discrete Appl. Math.235 (2018) 142-153. · Zbl 1375.05099 |
| [52] | R. Luo and G. Yu, A note on strong edge-coloring of 2-degenerate graphs, preprint (2012), arXiv:1212.6092 [math.CO]. |
| [53] | B. Lužar, M. Mochovčiaková, R. Soták and R. Škrekovski, Strong edge-coloring of subcubic bipartite graphs, preprint (2013), arXiv:1311.6668 [math.CO]. |
| [54] | Ma, H., Miao, Z., Zhu, H., Zhang, J. and Luo, R., Strong list edge coloring of subcubic graphs, Math. Probl. Eng.2013Article ID 16501. · Zbl 1296.05075 |
| [55] | Mahdian, M., The strong chromatic index of \(C_4\)-free graphs, Random Structures Algorithms17 (2000) 357-375. · Zbl 0961.05022 |
| [56] | Mahdian, M., On the computational complexity of strong edge-coloring, Discrete Appl. Math.118 (2002) 239-248. · Zbl 1016.68062 |
| [57] | Maydanskiy, M., The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math.292 (2005) 131-141. · Zbl 1059.05051 |
| [58] | Molloy, M. and Reed, B., A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B69 (1997) 103-109. · Zbl 0880.05036 |
| [59] | Molloy, M. and Reed, B., Graph Colouring and the Probabilistic Method (Springer, Berlin, 2002). · Zbl 0987.05002 |
| [60] | Nakprasit, K., A note on the strong chromatic index of bipartite graphs, Discrete Math.308 (2008) 3726-3728. · Zbl 1155.05026 |
| [61] | Ruksasakchai, W. and Wang, T., List strong edge coloring of some classes of graphs, Austral. J. Combin.68 (2017) 106-117. · Zbl 1375.05106 |
| [62] | Sanders, D. P. and Zhao, Y., Planar graphs of maximum degree seven are class I, J. Combin. Theory, Ser. B83(2) (2001) 201-212. · Zbl 1024.05031 |
| [63] | Ślezayńska-Bowak, M., Clique number of the square of a line graph, Discrete Math.339(5) (2016) 1551-1556. · Zbl 1333.05260 |
| [64] | Steger, A. and Yu, M. L., On induced matchings, Discrete Math.120 (1993) 291-295. · Zbl 0787.05079 |
| [65] | Stockmeyer, L. J. and Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett.15 (1982) 14-19. · Zbl 0493.68039 |
| [66] | P. Valicov, On packing, colouring and identification problems, Data Structures and Algorithms [cs.DS]. Universit Sciences et Technologies — Bordeaux I, 2012 https://tel.archives-ouvertes.fr/tel-00801982. |
| [67] | Verclos, R. D. J. D., Kang, R. J. and Pastor, L., Colouring squares of claw-free graphs, Electron. Notes Discrete Math.61 (2017) 663-669. · Zbl 1379.05044 |
| [68] | Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Metody Diskret. Analiz3 (1964) 25-30. · Zbl 1539.05042 |
| [69] | Wang, T., Strong chromatic index of \(k\)-degenerate graphs, Discrete Math. Appl. Math.330 (2014) 17-19. · Zbl 1295.05111 |
| [70] | Wang, T. and Zhao, X., Odd graphs and its application on the strong edge-coloring, Appl. Math. Comput.325 (2018) 246-251. · Zbl 1428.05120 |
| [71] | Wang, Y., Shiu, W. C., Wang, W. and Chen, M., Planar graphs with maximum degree \(4\) are strongly \(1 9\)-edge-colorable, Discrete Math.341 (2018) 1629-1635. · Zbl 1384.05074 |
| [72] | Wu, J. and Lin, W., The strong chromatic index of a class of graphs, Discrete Math.308 (2008) 6254-6261. · Zbl 1214.05033 |
| [73] | Yu, G., Strong edge-colorings for \(k\)-degenerate graphs, Graphs Combin.31 (2015) 1815-1818. · Zbl 1321.05096 |
| [74] | C. Zang, The strong chromatic index of graphs with maximum degree \(\Delta \), preprint (2015), arXiv:1510.00785 [math.CO]. |
| [75] | Zhang, L., Every planar graph with maximum degree 7 is of class 1, Graphs Combin.16 (2000) 467-495. · Zbl 0988.05042 |
| [76] | Zhu, H. and Miao, Z., On strong list edge-coloring of subcubic graphs, Discrete Math.333 (2014) 6-13. · Zbl 1298.05138 |
| [77] | Zito, M., Induced matchings in regular graphs and trees, , Vol. 1665 (Springer, Berlin, 1999). · Zbl 0941.05052 |
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.
