Some Results on Edge Cover Coloring of Double Graphs


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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

Copyright © 2023 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.