M₂-Edge Colorings Of Cacti And Graph Joins

• Autorzy: Július Czap , Peter Šugerek , Jaroslav Ivančo
• Języki publikacji: EN

Abstrakty

EN

An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.

Słowa kluczowe

EN

cactus; edge coloring; graph join

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 59-69

Daty

wydano

2016-02-01

otrzymano

2014-12-12

poprawiono

2015-04-13

zaakceptowano

2015-04-13

online

2016-01-19

Twórcy

autor

Július Czap

• Department of Applied Mathematics and Business Informatics Faculty of Economics, Technical University of Košice, Němcovej 32, 040 01 Košice, Slovakia

autor

Peter Šugerek

• Department of Applied Mathematics and Business Informatics Faculty of Economics, Technical University of Košice, Němcovej 32, 040 01 Košice, Slovakia

autor

Jaroslav Ivančo

• Institute of Mathematics, P. J. Šafárik University, Jesenná 5, 040 01 Košice, Slovakia

Bibliografia

• [1] K. Budajová and J. Czap, M2-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013) 161–167. doi:10.12732/ijpam.v88i2.1[Crossref]
• [2] H. Choi and S.L. Hakimi, Scheduling file transfers for trees and odd cycles, SIAM J. Comput. 16 (1987) 162–168. doi:10.1137/0216013[Crossref]
• [3] E.G. Co man Jr., M.R. Garey, D.S. Johnson and A.S. LaPaugh, Scheduling file transfers, SIAM J. Comput. 14 (1985) 744–780. doi:10.1137/0214054[Crossref]
• [4] J. Czap, Mi-edge colorings of graphs, Appl. Math. Sciences 5 (2011) 2437–2442. doi:10.12988/ams[Crossref]
• [5] J. Czap, A note on M2-edge colorings of graphs, Opuscula Math. 35 (2015) 287–291. doi:10.7494/OpMath.2015.35.3.287[Crossref]
• [6] M. Gionfriddo, L. Milazzo and V. Voloshin, On the upper chromatic index of a multigraph, Comput. Sci. J. Moldova 10 (2002) 81–91.
• [7] S.L. Hakimi and O. Kariv, A generalization of edge-coloring in graphs, J. Graph Theory 10 (1986) 139–154. doi:10.1002/jgt.3190100202[Crossref]
• [8] H. Krawczyk and M. Kubale, An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE Trans. Comput. C-34 (1985) 869–872. doi:10.1109/TC.1985.1676647[Crossref]
• [9] S.I. Nakano, T. Nishizeki and N. Saito, On the f-coloring of multigraphs, IEEE Trans. Circuits Syst. 35 (1988) 345–353. doi:10.1109/31.1747[Crossref]
• [10] D. Sitton, Maximum matching in complete multipartite graphs, Furman Univ. Electronic J. Undergraduate Math. 2 (1996) 6–16.
• [11] R. Soták, Personal communication.
• [12] X. Zhang and G. Liu, f-colorings of some graphs of f-class 1, Acta Math. Sin. (Engl. Ser.) 24 (2008) 743–748. doi:10.1007/s10114-007-6194-9[Crossref]
• [13] X. Zhang and G. Liu, Some sufficient conditions for a graph to be of Cf 1, Appl. Math. Lett. 19 (2006) 38–44. doi:10.1016/j.aml.2005.03.006[Crossref]
• [14] X. Zhang and G. Liu, Some graphs of class 1 for f-colorings, Appl. Math. Lett. 21 (2008) 23–29. doi:10.1016/j.aml.2007.02.009[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1842