Geodesic
On $g_c$-colorings of nearly bipartite graphs
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 433-444 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2018.0477-16
Classification : 05C15
Keywords: edge coloring; nearly bipartite graph; edge covering coloring; $g_c$-coloring; edge cover decomposition 
@article{10_21136_CMJ_2018_0477_16,
     author = {Zhang, Yuzhuo and Zhang, Xia},
     title = {On $g_c$-colorings of nearly bipartite graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {433--444},
     year = {2018},
     volume = {68},
     number = {2},
     doi = {10.21136/CMJ.2018.0477-16},
     mrnumber = {3819182},
     zbl = {06890381},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0477-16/}
}
TY  - JOUR
AU  - Zhang, Yuzhuo
AU  - Zhang, Xia
TI  - On $g_c$-colorings of nearly bipartite graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 433
EP  - 444
VL  - 68
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0477-16/
DO  - 10.21136/CMJ.2018.0477-16
LA  - en
ID  - 10_21136_CMJ_2018_0477_16
ER  - 
%0 Journal Article
%A Zhang, Yuzhuo
%A Zhang, Xia
%T On $g_c$-colorings of nearly bipartite graphs
%J Czechoslovak Mathematical Journal
%D 2018
%P 433-444
%V 68
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0477-16/
%R 10.21136/CMJ.2018.0477-16
%G en
%F 10_21136_CMJ_2018_0477_16
Zhang, Yuzhuo; Zhang, Xia. On $g_c$-colorings of nearly bipartite graphs. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 433-444. doi: 10.21136/CMJ.2018.0477-16

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan Press, London (1976). | MR | JFM

[2] Gupta, R. P.: On decompositions of multi-graph into spanning subgraphs. Bull. Am. Math. Soc. 80 (1974), 500-502. | DOI | MR | JFM

[3] Holyer, I.: The NP-completeness of edge coloring. SIAM J. Comput. 10 (1981), 718-720. | DOI | MR | JFM

[4] Li, J., Liu, G.: On $f$-edge cover coloring of nearly bipartite graphs. Bull. Malays. Math. Sci. Soc. (2) 34 (2011), 247-253. | MR | JFM

[5] Nakano, S., Nishizeki, T.: Scheduling file transfers under port and channel constrains. Int. J. Found. Comput. Sci. 4 (1993), 101-115. | DOI | MR | JFM

[6] Song, H., Liu, G.: On $f$-edge cover-coloring of simple graphs. Acta Math. Sci., Ser. B, Engl. Ed. 25 (2005), 145-151. | DOI | MR | JFM

[7] Song, H., Liu, G.: $f$-edge cover-coloring of graphs. Acta Math. Sin. 48 (2005), 919-928 Chinese. | MR | JFM

[8] Wang, J., Zhang, X., Liu, G.: Edge covering coloring of nearly bipartite graphs. J. Appl. Math. Comput. 22 (2006), 435-440. | DOI | MR | JFM

[9] Xu, C., Jia, Y.: A note on edge-cover coloring of nearly bipartite graphs. Ars Comb. 91 (2009), 423-427. | MR | JFM

[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

[11] Zhang, X.: Vertex splitting for determining the $f$-chromatic class of simple graphs. Submitted.

Cité par Sources :