Geodesic
Point-distinguishing chromatic index of the union of paths
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 629-640 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $G$ be a simple graph. For a general edge coloring of a graph $G$ (i.e., not necessarily a proper edge coloring) and a vertex $v$ of $G$, denote by $S(v)$ the set (not a multiset) of colors used to color the edges incident to $v$. For a general edge coloring $f$ of a graph $G$, if $S(u)\neq S(v)$ for any two different vertices $u$ and $v$ of $G$, then we say that $f$ is a point-distinguishing general edge coloring of $G$. The minimum number of colors required for a point-distinguishing general edge coloring of $G$, denoted by $\chi _{0}(G)$, is called the point-distinguishing chromatic index of $G$. In this paper, we determine the point-distinguishing chromatic index of the union of paths and propose a conjecture.
Let $G$ be a simple graph. For a general edge coloring of a graph $G$ (i.e., not necessarily a proper edge coloring) and a vertex $v$ of $G$, denote by $S(v)$ the set (not a multiset) of colors used to color the edges incident to $v$. For a general edge coloring $f$ of a graph $G$, if $S(u)\neq S(v)$ for any two different vertices $u$ and $v$ of $G$, then we say that $f$ is a point-distinguishing general edge coloring of $G$. The minimum number of colors required for a point-distinguishing general edge coloring of $G$, denoted by $\chi _{0}(G)$, is called the point-distinguishing chromatic index of $G$. In this paper, we determine the point-distinguishing chromatic index of the union of paths and propose a conjecture.
DOI : 10.1007/s10587-014-0123-8
Classification : 05C15
Keywords: general edge coloring; point-distinguishing general edge coloring; point-distinguishing chromatic index 
@article{10_1007_s10587_014_0123_8,
     author = {Chen, Xiang'en},
     title = {Point-distinguishing chromatic index of the union of paths},
     journal = {Czechoslovak Mathematical Journal},
     pages = {629--640},
     year = {2014},
     volume = {64},
     number = {3},
     doi = {10.1007/s10587-014-0123-8},
     mrnumber = {3298551},
     zbl = {06391516},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0123-8/}
}
TY  - JOUR
AU  - Chen, Xiang'en
TI  - Point-distinguishing chromatic index of the union of paths
JO  - Czechoslovak Mathematical Journal
PY  - 2014
SP  - 629
EP  - 640
VL  - 64
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0123-8/
DO  - 10.1007/s10587-014-0123-8
LA  - en
ID  - 10_1007_s10587_014_0123_8
ER  - 
%0 Journal Article
%A Chen, Xiang'en
%T Point-distinguishing chromatic index of the union of paths
%J Czechoslovak Mathematical Journal
%D 2014
%P 629-640
%V 64
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0123-8/
%R 10.1007/s10587-014-0123-8
%G en
%F 10_1007_s10587_014_0123_8
Chen, Xiang'en. Point-distinguishing chromatic index of the union of paths. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 629-640. doi: 10.1007/s10587-014-0123-8

[1] Balister, P. N.: Packing circuits into $K_n$. Comb. Probab. Comput. 10 (2001), 463-499. | DOI | MR | Zbl

[2] Balister, P. N., Bollobás, B., Schelp, R. H.: Vertex distinguishing colorings of graphs with $\Delta(G)=2$. Discrete Math. 252 (2002), 17-29. | MR | Zbl

[3] Balister, P. N., Riordan, O. M., Schelp, R. H.: Vertex-distinguishing edge colorings of graphs. J. Graph Theory 42 (2003), 95-109. | DOI | MR | Zbl

[4] Bazgan, C., Harkat-Benhamdine, A., Li, H., Wo'zniak, M.: On the vertex-distinguishing proper edge-colorings of graphs. J. Comb. Theory, Ser. B 75 (1999), 288-301. | DOI | MR

[5] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge-colorings. J. Graph Theory 26 (1997), 73-82. | DOI | MR | Zbl

[6] Černý, J., Horňák, M., Soták, R.: Observability of a graph. Math. Slovaca 46 (1996), 21-31. | MR | Zbl

[7] Harary, F., Plantholt, M.: The point-distinguishing chromatic index. Graphs and Application, Proc. 1st Symp. Graph theory, Boulder/Colo. 1982 F. Harary et al. A Wiley-Interscience Publication John Wiley & Sons, New York (1985), 147-162. | MR | Zbl

[8] Horňák, M., Salvi, N. Z.: On the point-distinguishing chromatic index of complete bipartite graphs. Ars Comb. 80 (2006), 75-85. | MR | Zbl

[9] Horňák, M., Soták, R.: Asymptotic behaviour of the observability of $Q_n$. Discrete Math. 176 (1997), 139-148. | DOI | MR

[10] Horňák, M., Soták, R.: Localization of jumps of the point-distinguishing chromatic index of $K_{n,n}$. Discuss. Math., Graph Theory 17 (1997), 243-251. | DOI | MR | Zbl

[11] Horňák, M., Soták, R.: Observability of complete multipartite graphs with equipotent parts. Ars Comb. 41 (1995), 289-301. | MR | Zbl

[12] Horňák, M., Soták, R.: The fifth jump of the point-distinguishing chromatic index of $K_{n,n}$. Ars Comb. 42 (1996), 233-242. | MR

[13] Salvi, N. Z.: On the point-distinguishing chromatic index of $K_{n,n}$. Eleventh British Combinatorial Conference (London, 1987), Ars Comb. 25B (1988), 93-104. | MR

[14] Salvi, N. Z.: On the value of the point-distinguishing chromatic index of $K_{n,n}$. Twelfth British Combinatorial Conference (Norwich, 1989), Ars Comb. 29B (1990), 235-244. | MR

Cité par Sources :