M 2 -Edge Colorings Of Cacti And Graph Joins
Július Czap ; Peter Šugerek ; Jaroslav Ivančo
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 59-69 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:276969 
@article{bwmeta1.element.doi-10_7151_dmgt_1842,
     author = {J\'ulius Czap and Peter \v Sugerek and Jaroslav Ivan\v co},
     title = {
      M
      2
      -Edge Colorings Of Cacti And Graph Joins
    },
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {59-69},
     zbl = {1329.05104},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1842}
}

Július Czap; Peter Šugerek; Jaroslav Ivančo. 
      M
      2
      -Edge Colorings Of Cacti And Graph Joins
    . Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 59-69. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1842/

[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] | Zbl 1278.05096

[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] | Zbl 0635.68023

[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. | Zbl 1023.05058

[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] | Zbl 0601.05021

[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] | Zbl 0638.05024

[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] | Zbl 1155.05029

[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] | Zbl 1132.05026