Czechoslovak Mathematical Journal, first online, pp. 1-12

On $g_c$-colorings of nearly bipartite graphs

Yuzhuo Zhang, Xia Zhang

Received September 11, 2016.   First published February 8, 2018.

Abstract:  Let $G$ be a simple graph, let $d(v)$ denote the degree of a vertex $v$ and let $g$ be a nonnegative integer function on $V(G)$ with $0\leq g(v)\leq d(v)$ for each vertex $v\in\nobreak V(G)$. A $g_c$-coloring of $G$ is an edge coloring such that for each vertex $v\in V(G)$ and each color $c$, there are at least $g(v)$ edges colored $c$ incident with $v$. The $g_c$-chromatic index of $G$, denoted by $\chi'_{g_c}(G)$, is the maximum number of colors such that a $g_c$-coloring of $G$ exists. Any simple graph $G$ has the $g_c$-chromatic index equal to $\delta_g(G)$ or $\delta_g(G)-1$, where $\delta_g(G)= \min_{v\in V(G)}\lfloor{d(v)}/{g(v)}\rfloor$. A graph $G$ is nearly bipartite, if $G$ is not bipartite, but there is a vertex $u\in V(G)$ such that $G-u$ is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph $G$ to have $\chi'_{g_c}(G)=\delta_g(G)$. Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.
Keywords:  edge coloring; nearly bipartite graph; edge covering coloring; $g_c$-coloring; edge cover decomposition
Classification MSC:  05C15
DOI:  10.21136/CMJ.2018.0477-16

PDF available at:  Institute of Mathematics CAS

[1] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Macmillan Press, London (1976). MR 0411988 | Zbl 1226.05083
[2] R. P. Gupta: On decompositions of multi-graph into spanning subgraphs. Bull. Am. Math. Soc. 80 (1974), 500-502. DOI 10.1090/S0002-9904-1974-13468-3 | MR 0335367 | Zbl 0291.05113
[3] I. Holyer: The NP-completeness of edge coloring. SIAM J. Comput. 10 (1981), 718-720. DOI 10.1137/0210055 | MR 0635430 | Zbl 0473.68034
[4] J. Li, G. Liu: On $f$-edge cover coloring of nearly bipartite graphs. Bull. Malays. Math. Sci. Soc. (2) 34 (2011), 247-253. MR 2788398 | Zbl 1221.05149
[5] S. Nakano, T. Nishizeki: Scheduling file transfers under port and channel constrains. Int. J. Found. Comput. Sci. 4 (1993), 101-115. DOI 10.1142/S0129054193000079 | MR 1252522 | Zbl 0802.68015
[6] H. Song, G. Liu: On $f$-edge cover-coloring of simple graphs. Acta Math. Sci., Ser. B, Engl. Ed. 25 (2005), 145-151. MR 2119347 | Zbl 1064.05064
[7] H. Song, G. Liu: $f$-edge cover-coloring of graphs. Acta Math. Sin. 48 (2005), 919-928 Chinese. MR 2182283 | Zbl 1124.05311
[8] J. Wang, X. Zhang, G. Liu: Edge covering coloring of nearly bipartite graphs. J. Appl. Math. Comput. 22 (2006), 435-440. DOI 10.1007/BF02896491 | MR 2248471 | Zbl 1114.05042
[9] C. Xu, Y. Jia: A note on edge-cover coloring of nearly bipartite graphs. Ars Comb. 91 (2009), 423-427. MR 2501981 | Zbl 1224.05465
[10] X. Zhang: The correlation between the $f$-chromatic class and the $g_c$-chromatic class of a simple graph. Ars Comb. 135 (2017), 17-28. MR 3702241
[11] X. Zhang: Vertex splitting for determining the $f$-chromatic class of simple graphs. Submitted.

Affiliations:   Yuzhuo Zhang, Xia Zhang (corresponding author), School of Mathematics and Statistics, Shandong Normal University, 88 Wenhua E Rd, Lixia, Jinan 250358, P. R. China, e-mail:

PDF available at: