Share This Article:

Some Results on Edge Cover Coloring of Double Graphs

Abstract Full-Text HTML XML Download Download as PDF (Size:59KB) PP. 264-266
DOI: 10.4236/am.2012.33041    3,402 Downloads   5,709 Views   Citations


Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

J. Wang and Q. Ma, "Some Results on Edge Cover Coloring of Double Graphs," Applied Mathematics, Vol. 3 No. 3, 2012, pp. 264-266. doi: 10.4236/am.2012.33041.


[1] E. G. Coffman, J. M. R. Garey, D. S. Johnson, et al., “Scheduling File Transfers,” SIAM Journal on Computing, Vol. 14, No. 1, 1985, pp. 326-336.
[2] J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” MacMillan, London, 1976.
[3] R. P. Gupta, “On Decompositions of a Multigraph into Spanning Subgraphs,” Bulletin of the American Mathematical Society, Vol. 80, No. 3, 1974, pp. 500-502. doi:10.1090/S0002-9904-1974-13468-3
[4] J. H. Wang, X. Zhang and G. Z. Liu, “Edge Covering Coloring of Nearly Bipartite Graphs,” Journal of Applied Mathematics and Computing, Vol. 122, 2006, pp. 435440. doi:10.1007/BF02896491
[5] C. Q. Xu and G. Z. Liu, “A Note on the Edge Cover Chromatic Index of Multigraphs,” Discrete Mathematics, Vol. 308, No. 24, 2008, pp. 6564-6568. doi:10.1016/j.disc.2007.11.049
[6] A. J. W. Hilton and D. Werra, “A Sufficient Condition for Equitable Edge Coloring of Simple Graphs,” Discrete Mathematics, Vol. 128, No. 1-3, 1994, pp. 179-201. doi:10.1016/0012-365X(94)90112-0
[7] L. Y. Miao, “The Edge Cover Coloring of Graphs,” Ph.D. Thesis, Shandong University, Jinan, 2000.
[8] I. Holyer, “The NP-Completeness of Edge-Coloring,” SIAM Journal on Computing, Vol. 10, No. 1, 1981, pp. 718-720. doi:10.1137/0210055

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.