zbMATH — the first resource for mathematics

On the neighbour-distinguishing index of a graph. (English) Zbl 1107.05032
Summary: A proper edge colouring of a graph \(G\) is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges. It is proved that for any planar bipartite graph \(G\) with \(\Delta(G) \geq 12\) there is a neighbour-distinguishing edge colouring of \(G\) using at most \(\Delta(G)+1\) colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.
Reviewer: Reviewer (Berlin)

05C15 Coloring of graphs and hypergraphs
edge colouring
Full Text: DOI
[1] Balister, P. N., Bollobás, B., Schelp, R. H.: Vertex distinguishing colorings of graphs with \(\Delta\)(G)=2, Discrete Math. 252, 17–29 (2002) · Zbl 1005.05019
[2] Balister, P.N., Gyori, E., Lehel, J. Schelp, R.H.: Adjacent vertex distinguishing edge- colorings. preprint (2002)
[3] Balister, P. N., Kostochka, A., Li, H., Schelp, R. H.: Balanced edge colorings, J. Combin. Theory Ser. B 90, 3–20 (2004)
[4] Balister, P. N., Riordan, O.M., Schelp, R. H.: Vertex Distinguishing edge colorings of graphs. J. Graph Theory 42, 95–109 (2003) · Zbl 1008.05067
[5] Bazgan, C., Harkat-Benhamdine, A., Li, H., Woźniak, M.: On the vertex-distinguishing proper edge-colorings of graphs, J. Combin. Theory Ser. B 75, 288–301 (1999) · Zbl 0932.05036
[6] Bazgan, C., Harkat-Benhamdine, A., Li, H., Woźniak, M.: A note on the vertex-distinguishing proper colorings of graphs with large minimum degree. Discrete Math. 236, 37–42 (2001) · Zbl 0995.05063
[7] Burris, A. C.: Vertex-distinguishing edge-colorings, Ph.D. Dissertation, Memphis State University, 1993 · Zbl 0886.05068
[8] Burris A. C. and Schelp, R. H.: Vertex-distinguishing proper edge-colorings, J. Graph Theory 26(2), 73–82 (1997) · Zbl 0886.05068
[9] Černý, J., Horňák M., Soták, R.: Observability of a graph, Math. Slovaca 46, 21–31 (1996) · Zbl 0853.05040
[10] Favaron, O. Li, H., Schelp, R.H.: Strong edge colouring of graphs, Discrete Math. 159, 103–109 (1996) · Zbl 0859.05042
[11] Hatami, H., \(\Delta\)+300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B 95, 246–256 (2005) · Zbl 1075.05034
[12] Horňák, M., Soták, R.: Observability of complete multipartite graphs with equipotent parts, Ars Combin. 41, 289–301 (1995) · Zbl 0841.05032
[13] Horňák, M., Soták, R.: Asymptotic behaviour of the observability of Qn, Discrete Math. 176, 139–148 (1997) · Zbl 0890.05028
[14] McDiarmid, C. J. H., Sánchez-Arroyo, A.: Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124, 155–162 (1994) · Zbl 0791.05042
[15] 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.