The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs

Grant Fickes, Wing Hong Tony Wong

Abstract


The edge-distinguishing chromatic number (EDCN) of a graph G is the minimum positive integer k such that there exists a vertex coloring c : V(G)→{1, 2, …, k} whose induced edge labels {c(u),c(v)} are distinct for all edges uv. Previous work has determined the EDCN of paths, cycles, and spider graphs with three legs. In this paper, we determine the EDCN of petal graphs with two petals and a loop, cycles with one chord, and spider graphs with four legs. These are achieved by graph embedding into looped complete graphs.


Keywords


vertex coloring, edge-distinguishing, graph embedding, EDCN, caterpillars, petal graphs, chorded cycles, spiders

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.5

References

A. Aflaki, S. Akbari, K.J. Edwards, D.S. Eskandani, M. Jamaali, and H. Ravanbod, On harmonious colouring of trees, Electron. J. Combin. 19(1) (2012), #P3.

M. Aigner, E. Triesch, and Z. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, Ann. Disc. Math. 52 (1992), 1–9.

K. Al-Wahabi, R. Bari, F. Harary, and D. Ullman, The edge-distinguishing chromatic number of paths and cycles, Ann. Disc. Math. 41 (1989), 17–22.

P. Balister, B. Bollobás, and R. Schelp, Vertex distinguishing colorings of graphs with Δ(G)=2, Disc. Math. 252 (2002), 17–29.

C. Bazgan, A. Harkat-Benhamdine, H. Li, and M. Woźniak, On the vertex-distinguishing proper edge-colorings of graphs, J. Combin. Theory Ser. B 75 (1999), 288–301.

D. Beane, N. Biggs, and B. Wilson, The growth rate of the harmonious chromatic number, J. Graph Theory 13 (1989), 291–299.

B. Brunton, B. Wilson, and T. Griggs, Graphs which have n/2-minimal line-distinguishing colourings, Disc. Math. 155 (1996), 19–26.

K. Collins and A. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16.

T. Dvořák, I. Havel, and P. Liebl, Euler cycles in the complete graph K2m + 1, Disc. Math. 171 (1997), 89–102.

K. Edwards, The harmonious chromatic number of complete r-ary trees, Disc. Math. 203 (1999), 83–99.

G. Fickes and T.W.H. Wong, The edge-distinguishing chromatic number of spider graphs with three legs or bounded leg lengths, J. Combin. Math. Combin. Comput. 113 (2020), 165–181.

O. Frank, F. Harary, and M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin. 14 (1982), 241–252.

J. Hopcroft and M. Krishnamoorthy, On the harmonious coloring of graphs, SIAM J. Algebr. Disc. Methods 4 (1983), 306–311.

J. Mitchem, On the harmonious chromatic number of a graph, Disc. Math. 74 (1989), 151–157.

J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11.1 (2004), #R63.

N. Zagaglia Salvi, A note on the line-distinguishing chromatic number and the chromatic index of a graph, J. Graph Theory 17 (1993), 589–591.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats