Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
general edge coloring; point-distinguishing general edge coloring; point-distinguishing chromatic index
general edge coloring; point-distinguishing general edge coloring; point-distinguishing chromatic index
Summary:
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.
References:
[1] Balister, P. N.: Packing circuits into $K_n$. Comb. Probab. Comput. 10 (2001), 463-499. DOI 10.1017/S0963548301004771 | MR 1869841 | Zbl 1113.05309
[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 1907743 | Zbl 1005.05019
[3] Balister, P. N., Riordan, O. M., Schelp, R. H.: Vertex-distinguishing edge colorings of graphs. J. Graph Theory 42 (2003), 95-109. DOI 10.1002/jgt.10076 | MR 1953223 | Zbl 1008.05067
[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 10.1006/jctb.1998.1884 | MR 1676894
[5] Burris, A. C., Schelp, R. H.: Vertex-distinguishing 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 | MR 1469354 | Zbl 0886.05068
[6] Černý, J., Horňák, M., Soták, R.: Observability of a graph. Math. Slovaca 46 (1996), 21-31. MR 1414406 | Zbl 0853.05040
[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 0778404 | Zbl 0562.05023
[8] Horňák, M., Salvi, N. Z.: On the point-distinguishing chromatic index of complete bipartite graphs. Ars Comb. 80 (2006), 75-85. MR 2243079 | Zbl 1224.05174
[9] Horňák, M., Soták, R.: Asymptotic behaviour of the observability of $Q_n$. Discrete Math. 176 (1997), 139-148. DOI 10.1016/S0012-365X(96)00292-0 | MR 1477284
[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 10.7151/dmgt.1051 | MR 1627943 | Zbl 0906.05025
[11] Horňák, M., Soták, R.: Observability of complete multipartite graphs with equipotent parts. Ars Comb. 41 (1995), 289-301. MR 1365173 | Zbl 0841.05032
[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 1386944
[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 0942468
[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 1412879
Search
Partner of
