×

On generalisations of the AVD conjecture to digraphs. (English) Zbl 1459.05099

Summary: Given an undirected graph, in the AVD (edge-colouring) Conjecture, the goal is to find a proper edge-colouring with the least number of colours such that every two adjacent vertices are incident to different sets of colours. More precisely, the conjecture says that, a few exceptions apart, every graph \(G\) should admit such an edge-colouring with at most \(\Delta (G)+2\) colours. Several aspects of interest behind this problem have been investigated over the recent years, including verifications of the conjecture for particular graph classes, general approximations of the conjecture, and multiple generalisations. In this paper, following a recent work of E. Sopena and M. Woźniak [“A note on the neighbour-distinguishing index of digraphs”, Preprint, arXiv:1909.10240], generalisations of the AVD Conjecture to digraphs are investigated. More precisely, four of the several possible ways of generalising the conjecture are focused upon. We completely settle one of our four variants, while, for the three remaining ones, we provide partial results.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Akbari, S.; Bidkhori, H.; Nosrati, N., r-strong edge colorings of graphs, Discr. Math., 306, 3005-3010 (2006) · Zbl 1112.05035
[2] Balister, PN; Győri, E.; Lehel, J.; Schelp, RH, Adjacent vertex distinguishing edge-colorings, SIAM J. Discr. Math., 21, 237-250 (2007) · Zbl 1189.05056
[3] Barme, E.; Bensmail, J.; Przybyło, J.; Woźniak, M., On a directed variation of the 1-2-3 and 1-2 Conjectures, Discr. Appl. Math., 217, 123-131 (2017) · Zbl 1358.05122
[4] Baudon, O.; Bensmail, J.; Sopena, É., An oriented version of the 1-2-3 conjecture, Discuss. Math. Graph Theory, 35, 1, 141-156 (2015) · Zbl 1326.05043
[5] Bensmail, J.; Szabo Lyngsie, K., 1-2-3 Conjecture in digraphs: more results and directions, Discr. Appl. Math., 284, 124-137 (2020) · Zbl 1443.05079
[6] Borowiecki, M.; Grytczuk, J.; Pilśniak, M., Coloring chip configurations on graphs and digraphs, Inf. Process. Lett., 112, 1-4 (2012) · Zbl 1232.05074
[7] Burris, AC; Schelp, RH, Vertex-distinguishing proper edge-colorings, J. Graph Theory, 26, 2, 73-82 (1997) · Zbl 0886.05068
[8] Černy, J.; Horňak, M.; Soták, R., Observability of a graph, Math. Slovaca, 46, 21-31 (1996) · Zbl 0853.05040
[9] Erdős, P., Nešetřil, J.: Irregularities of partitions. G. Halász, V.T. Sós, Eds., [Problem], pp. 162-163 (1989)
[10] Holyer, IJ, The NP-completeness of edge coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034
[11] Horňak, M.; Przybyło, J.; Woźniak, M., A note on a directed version of the 1-2-3 conjecture, Discr. Appl. Math., 236, 472-476 (2018) · Zbl 1377.05060
[12] König, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann., 77, 4, 453-465 (1916) · JFM 46.0146.03
[13] Li, H.; Bai, Y.; He, W.; Sun, Q., Vertex-distinguishing proper arc colorings of digraphs, Discr. Appl. Math., 209, 276-286 (2016) · Zbl 1339.05140
[14] Seamone, B.: The 1-2-3 Conjecture and related problems: a survey. Preprint, 2012. arXiv:1211.5122
[15] Sopena, É., Woźniak, M.: A note on the neighbour-distinguishing index of digraphs. Preprint, 2019. Available online at arXiv:1909.10240
[16] Vizing, VG, On an estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz., 3, 25-30 (1964)
[17] Vizing, VG, The chromatic class of a multigraph, Kibernetika, 3, 29-39 (1965)
[18] West, DB, Introduction to Graph Theory (1996), New Jersey: Prentice Hall, New Jersey · Zbl 0845.05001
[19] Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15, 623-626 (2002) · Zbl 1008.05050
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.