| Title:
|
On $g_c$-colorings of nearly bipartite graphs (English) |
| Author:
|
Zhang, Yuzhuo |
| Author:
|
Zhang, Xia |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
433-444 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
edge coloring |
| Keyword:
|
nearly bipartite graph |
| Keyword:
|
edge covering coloring |
| Keyword:
|
$g_c$-coloring |
| Keyword:
|
edge cover decomposition |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 06890381 |
| idMR:
|
MR3819182 |
| DOI:
|
10.21136/CMJ.2018.0477-16 |
| . |
| Date available:
|
2018-06-11T10:54:17Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147227 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.Macmillan Press, London (1976). Zbl 1226.05083, MR 0411988 |
| Reference:
|
[2] Gupta, R. P.: On decompositions of multi-graph into spanning subgraphs.Bull. Am. Math. Soc. 80 (1974), 500-502. Zbl 0291.05113, MR 0335367, 10.1090/S0002-9904-1974-13468-3 |
| Reference:
|
[3] Holyer, I.: The NP-completeness of edge coloring.SIAM J. Comput. 10 (1981), 718-720. Zbl 0473.68034, MR 0635430, 10.1137/0210055 |
| Reference:
|
[4] Li, J., Liu, G.: On $f$-edge cover coloring of nearly bipartite graphs.Bull. Malays. Math. Sci. Soc. (2) 34 (2011), 247-253. Zbl 1221.05149, MR 2788398 |
| Reference:
|
[5] Nakano, S., Nishizeki, T.: Scheduling file transfers under port and channel constrains.Int. J. Found. Comput. Sci. 4 (1993), 101-115. Zbl 0802.68015, MR 1252522, 10.1142/S0129054193000079 |
| Reference:
|
[6] Song, H., Liu, G.: On $f$-edge cover-coloring of simple graphs.Acta Math. Sci., Ser. B, Engl. Ed. 25 (2005), 145-151. Zbl 1064.05064, MR 2119347, 10.1016/S0252-9602(17)30271-0 |
| Reference:
|
[7] Song, H., Liu, G.: $f$-edge cover-coloring of graphs.Acta Math. Sin. 48 (2005), 919-928 Chinese. Zbl 1124.05311, MR 2182283 |
| Reference:
|
[8] Wang, J., Zhang, X., Liu, G.: Edge covering coloring of nearly bipartite graphs.J. Appl. Math. Comput. 22 (2006), 435-440. Zbl 1114.05042, MR 2248471, 10.1007/BF02896491 |
| Reference:
|
[9] Xu, C., Jia, Y.: A note on edge-cover coloring of nearly bipartite graphs.Ars Comb. 91 (2009), 423-427. Zbl 1224.05465, MR 2501981 |
| Reference:
|
[10] Zhang, X.: 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 |
| Reference:
|
[11] Zhang, X.: Vertex splitting for determining the $f$-chromatic class of simple graphs.Submitted. |
| . |
