M 2 -Edge Colorings Of Cacti And Graph Joins

Július Czap; Peter Šugerek; Jaroslav Ivančo

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 59-69
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Július Czap, Peter Šugerek, and Jaroslav Ivančo. " M 2 -Edge Colorings Of Cacti And Graph Joins ." Discussiones Mathematicae Graph Theory 36.1 (2016): 59-69. <http://eudml.org/doc/276969>.

@article{JúliusCzap2016,
abstract = {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.},
author = {Július Czap, Peter Šugerek, Jaroslav Ivančo},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cactus; edge coloring; graph join},
language = {eng},
number = {1},
pages = {59-69},
title = { M 2 -Edge Colorings Of Cacti And Graph Joins },
url = {http://eudml.org/doc/276969},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Július Czap
AU - Peter Šugerek
AU - Jaroslav Ivančo
TI - M 2 -Edge Colorings Of Cacti And Graph Joins
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 59
EP - 69
AB - 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.
LA - eng
KW - cactus; edge coloring; graph join
UR - http://eudml.org/doc/276969
ER -

References

top
  1. [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] Zbl1278.05096
  2. [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] Zbl0635.68023
  3. [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. [4] J. Czap, Mi-edge colorings of graphs, Appl. Math. Sciences 5 (2011) 2437–2442. doi:10.12988/ams[Crossref] 
  5. [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. [6] M. Gionfriddo, L. Milazzo and V. Voloshin, On the upper chromatic index of a multigraph, Comput. Sci. J. Moldova 10 (2002) 81–91. Zbl1023.05058
  7. [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] Zbl0601.05021
  8. [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. [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] Zbl0638.05024
  10. [10] D. Sitton, Maximum matching in complete multipartite graphs, Furman Univ. Electronic J. Undergraduate Math. 2 (1996) 6–16. 
  11. [11] R. Soták, Personal communication. 
  12. [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] Zbl1155.05029
  13. [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. [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] Zbl1132.05026

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.