Abstract
An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V(G) at most f(v) times. The minimum number of colors needed to f-color G is called the f-chromatic index of G, and denoted by χ′ f (G). Any simple graph G has f-chromatic index equal to Δ f (G) or Δ f (G) + 1, where \(\Delta_{f}(G)=\max_{v\in V(G)}\{\lceil\frac{d(v)}{f(v)}\rceil\}\). If χ′ f (G) = Δ f (G), then G is of f-class 1; otherwise G is of f-class 2. In this paper, we show that if f(v) is positive and even for all \(v\in V_0^*(G)\cup N_G(V_0^*(G))\), then G is of f-class 1, where \(V^{*}_{0}(G)=\{v\in V(G):\frac{d(v)}{f(v)}=\Delta_{f}(G)\}\) and \(N_G(V_0^*(G))=\{v\in V(G):uv\in E(G), u\in V_0^*(G)\}\). This result improves the simple graph version of a result of Hakimi and Kariv [4].
This research is supported by NSFC(10471078, 60673047) and RSDP(20040422004) and NSF of Hebei(A2007000002) of China.
Chapter PDF
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London (1976)
Choi, H., Hakimi, S.L.: Scheduling file transfers for trees and odd cycles. SIAM J. Comput. 16(1), 162–168 (1987)
Coffman, J.E.G., Garey, M.R., Johnson, D.S., LaPaugn, A.S.: Scheduling file transfers. SIAM J. Comput. 14(3), 744–780 (1985)
Hakimi, S.L., Kariv, O.: A generalization of edge-coloring in graphs. J. Graph Theory 10, 139–154 (1986)
Holyer, I.J.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720 (1981)
Krawczyk, H., Kubale, M.: An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput. 34, 869–872 (1985)
Liu, G.Z., Hou, J.F., Cai, J.S.: Some results about f-critical graphs. Networks (accepted)
Nakano, S., Nishizeki, T., Saito, N.: On the f-coloring of multigraphs. IEEE Trans. Circuit and Syst. 35(3), 345–353 (1988)
Vizing, V.G.: On an estimate of the chromatic class of a p-graph (Russian). Discret Analiz. 3, 25–30 (1964)
Zhang, X., Liu, G.Z.: The classification of complete graphs K n on f-coloring. J. Applied Mathematics & Computing 19(1-2), 127–133 (2005)
Zhang, X., Liu, G.Z.: Some sufficient conditions for a graph to be C f 1. Applied Mathematics Letters 19, 38–44 (2006)
Zhang, X., Wang, J.H., Liu, G.Z.: The classification of regular graphs on f-colorings. Ars Combinatoria (to appear)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Zhang, X., Liu, G. (2007). A Class of Graphs of f-Class 1. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2007. ICCS 2007. Lecture Notes in Computer Science, vol 4489. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72588-6_59
Download citation
DOI: https://doi.org/10.1007/978-3-540-72588-6_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72587-9
Online ISBN: 978-3-540-72588-6
eBook Packages: Computer ScienceComputer Science (R0)