# Vertex-distinguishing edge-colorings of linear forests

Sylwia Cichacz; Jakub Przybyło

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 1, page 95-103
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSylwia Cichacz, and Jakub Przybyło. "Vertex-distinguishing edge-colorings of linear forests." Discussiones Mathematicae Graph Theory 30.1 (2010): 95-103. <http://eudml.org/doc/270952>.

@article{SylwiaCichacz2010,

abstract = {In the PhD thesis by Burris (Memphis (1993)), a conjecture was made concerning the number of colors c(G) required to edge-color a simple graph G so that no two distinct vertices are incident to the same multiset of colors. We find the exact value of c(G) - the irregular coloring number, and hence verify the conjecture when G is a vertex-disjoint union of paths. We also investigate the point-distinguishing chromatic index, χ₀(G), where sets, instead of multisets, are required to be distinct, and determine its value for the same family of graphs.},

author = {Sylwia Cichacz, Jakub Przybyło},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {irregular edge-coloring; vertex-distinguishing edge-coloring; point-distinguishing chromatic index},

language = {eng},

number = {1},

pages = {95-103},

title = {Vertex-distinguishing edge-colorings of linear forests},

url = {http://eudml.org/doc/270952},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Sylwia Cichacz

AU - Jakub Przybyło

TI - Vertex-distinguishing edge-colorings of linear forests

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 1

SP - 95

EP - 103

AB - In the PhD thesis by Burris (Memphis (1993)), a conjecture was made concerning the number of colors c(G) required to edge-color a simple graph G so that no two distinct vertices are incident to the same multiset of colors. We find the exact value of c(G) - the irregular coloring number, and hence verify the conjecture when G is a vertex-disjoint union of paths. We also investigate the point-distinguishing chromatic index, χ₀(G), where sets, instead of multisets, are required to be distinct, and determine its value for the same family of graphs.

LA - eng

KW - irregular edge-coloring; vertex-distinguishing edge-coloring; point-distinguishing chromatic index

UR - http://eudml.org/doc/270952

ER -

## References

top- [1] M. Aigner and E. Triesch, Irregular assignments and two problems á la Ringel, in: Topics in Combinatorics and Graph Theory, dedicated to G. Ringel, Bodendiek, Henn, eds. (Physica Verlag Heidelberg, 1990) 29-36.
- [2] P.N. Balister, Packing Circuits into Kₙ, Combin. Probab. Comput. 10 (2001) 463-499, doi: 10.1017/S0963548301004771. Zbl1113.05309
- [3] P.N. Balister, B. Bollobás and R.H. Schelp, Vertex-distinguishing edge-colorings of graphs with Δ(G) = 2, Discrete Math. 252 (2002) 17-29, doi: 10.1016/S0012-365X(01)00287-4. Zbl1005.05019
- [4] A.C. Burris, Vertex-distinguishing edge-colorings (PhD Thesis, Memphis, 1993).
- [5] A.C. Burris and R.H. Schelp, Vertex-distiguishing proper edge-colorings, J. Graph Theory 26 (1997) 73-82, doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C Zbl0886.05068
- [6] J. Cerný, M. Hornák and R. Soták, Observability of a graph, Math. Slovaca 46 (1996) 21-31. Zbl0853.05040
- [7] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular Networks, Congressus Numerantium 64 (1988) 187-192.
- [8] S. Cichacz, J. Przybyło and M. Woźniak, Decompositions of pseudographs into closed trails of even sizes, Discrete Math. 309 (2009) 4903-4908, doi: 10.1016/j.disc.2008.04.024. Zbl1218.05123
- [9] S. Cichacz, J. Przybyło and M. Woźniak, Irregular edge-colorings of sums of cycles of even lengths, Australas. J. Combin. 40 (2008) 41-56. Zbl1143.05024
- [10] F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications, Proc. 1st Symp. Graph Theory, Boulder/Colo. 1982, (1985) 147-162.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.