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

Abstract

top
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.

How to cite

top

Sylwia 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. [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. [2] P.N. Balister, Packing Circuits into Kₙ, Combin. Probab. Comput. 10 (2001) 463-499, doi: 10.1017/S0963548301004771. Zbl1113.05309
  3. [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. [4] A.C. Burris, Vertex-distinguishing edge-colorings (PhD Thesis, Memphis, 1993). 
  5. [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. [6] J. Cerný, M. Hornák and R. Soták, Observability of a graph, Math. Slovaca 46 (1996) 21-31. Zbl0853.05040
  7. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.