Abstract
A proper edge-coloring of a graph defines at each vertex the set of colors of its incident edges. This set is called the palette of the vertex. In this paper we are interested in the minimum number of palettes taken over all possible proper colorings of a graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Burris A.C., Schelp R.H.: Vertex-distinguishing proper edge-colourings. J. Graph Theory 26, 73–82 (1997)
Černý J., Horňák M., Soták R.: Observability of a graph. Math. Slovaca 46, 21–31 (1996)
Edwards K., Horňák M., Woźniak M.: On the neighbour-distinguishing index of a graph. Graph Combin. 22, 341–350 (2006)
Woolbright D.E., Fu H-L.: On the existence of rainbows in 1-factorizat-ions of K 2n . J. Combin. Des 6, 1–20 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the first author was supported by Science and Technology Assistance Agency under the contract No. APVV-0023-10 and by Grant VEGA 1/0428/10. The research of the remaining three authors was partially supported by Polish Ministry of Science and Higher Education.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Horňák, M., Kalinowski, R., Meszka, M. et al. Minimum Number of Palettes in Edge Colorings. Graphs and Combinatorics 30, 619–626 (2014). https://doi.org/10.1007/s00373-013-1298-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1298-8