×

Incidence coloring of Mycielskians with fast algorithm. (English) Zbl 1522.05095

An incidence of an undirected graph \(G\) is a pair \((v,e)\) where \(v\) is a vertex of \(G\) and \(e\) an edge of \(G\) incident with \(v\). Two incidences \((v,e) \) and \((w,f)\) are adjacent if one of the following holds: (i) \(v=w\), (ii) \(e=f\) or (iii) \(vw\in \{e.f\}\). An incidence coloring of \(G\) assigns a color to each incidence of \(G\) in such a way that adjacent incidences get distinct colors. The smallest number of colors required for such a coloring is called the incidence chromatic number of \(G\), and is denoted by \(\chi _{i}(G)\).
The notion of the incidence coloring was introduced by R. A. Brualdi and J. J. Q. Massey [Discrete Math. 122, No. 1–3, 51–58 (1993; Zbl 0790.05026)], where the authors conjectured that \(\chi _{i}(G)\leq \Delta (G)+2\) holds for every graph \(G\). The conjecture was disproved [B. Guiduli, ibid. 163, No. 1–3, 275–278 (1997; Zbl 0871.05022)], but this inequality seems to hold for many of the commonly considered graph classes.
The author of this paper conjectures that the inequality is true for Mycielskians of any graph, and confirms it for graphs with relatively small maximum degree \(\Delta .\)

MSC:

05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Algor, I.; Alon, N., The star arboricity of graphs, Discrete Math., 75, 11-22 (1989) · Zbl 0684.05033
[2] Barrett, C. L.; Istrate, G.; Kumar, V. S.A.; Marathe, M. V.; Thite, S.; Thulasidasan, S., Strong edge coloring for channel assignment in wireless radio networks, (Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PERCOMW’06 (2006)), 5 pages
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory, GTM, vol. 244 (2008), Springer · Zbl 1134.05001
[4] Brualdi, R. A.; Quinn Massey, J. J., Incidence and strong edge colorings of graphs, Discrete Math., 122, 51-58 (1993) · Zbl 0790.05026
[5] Cui, X.; Shun, W.; Liu, X.; Wang, H., A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles, Theor. Comput. Sci., 863, 53-58 (2020) · Zbl 1455.05016
[6] Chicano, F.; Whitley, L. D.; Alba, E.; Luna, F., Elementary landscape decomposition of the frequency assignment problem, Theor. Comput. Sci., 412, 6002-6019 (2011) · Zbl 1229.90154
[7] Deng, X.; Shao, Z.; Zhang, H.; Yang, W., The \((d, 1)\)-total labelling of Sierpiń ski-like graphs, Appl. Math. Comput., 361, 484-492 (2019) · Zbl 1428.05266
[8] Gregor, P.; Lužar, B.; Soták, R., On incidence coloring conjecture in Cartesian products of graphs, Discrete Appl. Math., 213, 93-100 (2016) · Zbl 1344.05117
[9] Guiduli, B., On incidence coloring and star arboricity of graphs, Discrete Math., 163, 275-278 (1997) · Zbl 0871.05022
[10] Guan, X.; Zhang, S.; Li, R.; Chen, L.; Yang, W., Anti-k-labeling of graphs, Appl. Math. Comput., 363, Article #124549 pp. (2019) · Zbl 1433.05268
[11] Hosseini Dolama, M.; Sopena, É., On the maximum average degree and the incidence chromatic number of a graph, Discrete Math. Theor. Comput. Sci., 7, 203-216 (2005) · Zbl 1153.05318
[12] Hosseini Dolama, M.; Sopena, É.; Zhu, X., Incidence coloring of k-degenerated graphs, Discrete Math., 283, 1-3, 121-128 (2004) · Zbl 1064.05057
[13] Huang, C. I.; Wang, Y. L.; Chung, S. S., The incidence coloring number of meshes, Comput. Math. Appl., 48, 1643-1649 (2004) · Zbl 1062.05059
[14] Janczewski, R.; Malafiejskaa, A.; Malafiejski, M., On incidence coloring of complete multipartite and subcubic bipartite graphs, Discuss. Math., Graph Theory, 38, 107-119 (2018) · Zbl 1377.05062
[15] Kardoš, F.; Maceková, M.; Mockovčiaková, M.; Sopena, É.; Soták, R., Incidence coloring - cold cases, Discuss. Math., Graph Theory, 40, 345-354 (2020) · Zbl 1430.05037
[16] Meng, X.; Guo, J.; Su, B., Incidence coloring of pseudo-Halin graphs, Discrete Math., 312, 3276-3283 (2012) · Zbl 1252.05068
[17] Misra, J.; Gries, D., A constructive proof of Vizing’s theorem, Inf. Process. Lett., 41, 3, 131-133 (1992) · Zbl 0795.68157
[18] Nakprasit, K.; Nakprasit, K., Incidence colorings of the powers of cycles, Int. J. Pure Appl. Math., 76, 1, 143-148 (2012) · Zbl 1247.05085
[19] Niu, B.; Zhang, X., On \((p, 1)\)-total labelling of some 1-planar graphs, Discuss. Math., Graph Theory, 41, 531-558 (2021) · Zbl 1458.05231
[20] Pai, K. J.; Chang, J. M.; Yang, J. S.; Wu, R. Y., Incidence coloring on hypercubes, Theor. Comput. Sci., 557, 59-65 (2014) · Zbl 1339.05144
[21] Shiu, W. C.; Lam, P. C.P.; Chen, D.-L., On incidence coloring for some cubic graphs, Discrete Math., 252, 259-266 (2002) · Zbl 0999.05045
[22] Sopena, É., The incidence coloring page
[23] Sopena, É.; Wu, J., The incidence chromatic number of toroidal grids, Discuss. Math., Graph Theory, 33, 315-3227 (2013) · Zbl 1304.05053
[24] Yi, C.-W., Maximum scan statistics and channel assignment problems in homogeneous wireless networks, Theor. Comput. Sci., 410, 2223-2233 (2009) · Zbl 1183.68064
[25] Zhu, J.; Bu, Y., List r-dynamic coloring of sparse graphs, Theor. Comput. Sci., 817, 1-11 (2020) · Zbl 1472.05060
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.