×

On the automorphic chromatic index of a graph. (English) Zbl 1221.05138

Summary: In this paper we define the automorphic \(H\)-chromatic index of a graph \(\Gamma \) as the minimum integer \(m\) for which \(\Gamma \) has a proper edge-coloring with \(m\) colors which is preserved by a given automorphism group \(H\) of \(\Gamma \). After the description of some properties, we determine upper bounds for this index when \(H\) is a cyclic group of prime order. We also show that these upper bounds are best possible in a number of instances.

MSC:

05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M.O., Collins, K.L.: Symmetry breaking in graphs. Electron. J. Combin. 3, #R18 (1996) · Zbl 0851.05088
[2] Baumann U., Lesch M.: Transitive groups of partition preserving automorphisms of graphs with edge colourings. Wiss. Z. Tech. Hochsch. Ilmenau 34(2), 33–38 (1988) · Zbl 0657.05035
[3] Baumann U., Lesch M., Schmeichel I.: Farb-und zerlegungstreue Automorphismen von Graphen. Math. Nachr. 134, 161–167 (1987) · Zbl 0633.05028 · doi:10.1002/mana.19871340111
[4] Baumann U., Lesch M., Schmeichel I.: Remarkable groups of graphs with edge colorings. Math. Nachr. 148, 175–182 (1990) · Zbl 0722.05037
[5] Cameron, P.J.: Automorphism groups of graphs. In: Selected Topics in Graph Theory 2, pp. 89–127. Academic Press, London (1983) · Zbl 0536.05037
[6] Cameron P.J., Korchmaros G.: One-factorizations of the complete graphs with a doubly transitive automorphism group. Bull. Lond. Math. Soc. 25, 1–6 (1993) · Zbl 0795.05069 · doi:10.1112/blms/25.1.1
[7] Chvàtal V., Sichler J.: Chromatic automorphisms of graphs. J. Combin. Theory Ser. B 14, 209–215 (1973) · Zbl 0264.05118 · doi:10.1016/0095-8956(73)90004-X
[8] Collins, K.L., Trenk, A.N.: The distinguishing chromatic number. Electron. J. Combin. 13, #R16 (2006) · Zbl 1081.05033
[9] Giudici, M., Li, C.H.: On finite edge-primitive and edge-quasiprimitive graphs. J. Combin. Theory B. doi: 10.1016/j.jctb.2009.09.00.1 · Zbl 1216.05053
[10] Harary F.: Methods of destroying the symmetries of a graph. Bull. Malays. Math. Sci. Soc. 24(2), 183–191 (2001) · Zbl 1020.05033
[11] Harary F.: The automorphism group of a hypercube. J. UCS 6(1), 136–138 (2000) · Zbl 0960.68130
[12] Schmeichel, I.: Automorphismen von Graphen mit zulässiger Kantenfärbung \({\phi}\) . In: 2nd Colloquium for Geometry and Combinatorics, Part 1, vol. 2, pp. 244–246 (1983)
[13] West D.: Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River (1996) · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.