On g c -colorings of nearly bipartite graphs

Yuzhuo Zhang; Xia Zhang

Czechoslovak Mathematical Journal (2018)

  • Volume: 68, Issue: 2, page 433-444
  • ISSN: 0011-4642

Abstract

top
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 ≤ g ( v ) ≤ d ( v ) for each vertex v ∈ V ( G ) . A g c -coloring of G is an edge coloring such that for each vertex v ∈ 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 χ 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 δ g ( G ) or δ g ( G ) - 1 , where δ g ( G ) = min v ∈ V ( G ) ⌊ d ( v ) / g ( v ) ⌋ . A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V ( G ) such that G - u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ g c ' ( G ) = δ g ( G ) . Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.

How to cite

top

Zhang, Yuzhuo, and Zhang, Xia. "On $g_c$-colorings of nearly bipartite graphs." Czechoslovak Mathematical Journal 68.2 (2018): 433-444. <http://eudml.org/doc/294472>.

@article{Zhang2018,
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\le g(v)\le d(v)$ for each vertex $v\in 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 ^\{\prime \}_\{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 ^\{\prime \}_\{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.},
author = {Zhang, Yuzhuo, Zhang, Xia},
journal = {Czechoslovak Mathematical Journal},
keywords = {edge coloring; nearly bipartite graph; edge covering coloring; $g_c$-coloring; edge cover decomposition},
language = {eng},
number = {2},
pages = {433-444},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On $g_c$-colorings of nearly bipartite graphs},
url = {http://eudml.org/doc/294472},
volume = {68},
year = {2018},
}

TY - JOUR
AU - Zhang, Yuzhuo
AU - Zhang, Xia
TI - On $g_c$-colorings of nearly bipartite graphs
JO - Czechoslovak Mathematical Journal
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 2
SP - 433
EP - 444
AB - 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\le g(v)\le d(v)$ for each vertex $v\in 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 ^{\prime }_{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 ^{\prime }_{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.
LA - eng
KW - edge coloring; nearly bipartite graph; edge covering coloring; $g_c$-coloring; edge cover decomposition
UR - http://eudml.org/doc/294472
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Macmillan Press, London (1976). (1976) Zbl1226.05083MR0411988
  2. Gupta, R. P., 10.1090/S0002-9904-1974-13468-3, Bull. Am. Math. Soc. 80 (1974), 500-502. (1974) Zbl0291.05113MR0335367DOI10.1090/S0002-9904-1974-13468-3
  3. Holyer, I., 10.1137/0210055, SIAM J. Comput. 10 (1981), 718-720. (1981) Zbl0473.68034MR0635430DOI10.1137/0210055
  4. Li, J., Liu, G., On f -edge cover coloring of nearly bipartite graphs, Bull. Malays. Math. Sci. Soc. (2) 34 (2011), 247-253. (2011) Zbl1221.05149MR2788398
  5. Nakano, S., Nishizeki, T., 10.1142/S0129054193000079, Int. J. Found. Comput. Sci. 4 (1993), 101-115. (1993) Zbl0802.68015MR1252522DOI10.1142/S0129054193000079
  6. Song, H., Liu, G., 10.1016/S0252-9602(17)30271-0, Acta Math. Sci., Ser. B, Engl. Ed. 25 (2005), 145-151. (2005) Zbl1064.05064MR2119347DOI10.1016/S0252-9602(17)30271-0
  7. Song, H., Liu, G., f -edge cover-coloring of graphs, Acta Math. Sin. 48 (2005), 919-928 Chinese. (2005) Zbl1124.05311MR2182283
  8. Wang, J., Zhang, X., Liu, G., 10.1007/BF02896491, J. Appl. Math. Comput. 22 (2006), 435-440. (2006) Zbl1114.05042MR2248471DOI10.1007/BF02896491
  9. Xu, C., Jia, Y., A note on edge-cover coloring of nearly bipartite graphs, Ars Comb. 91 (2009), 423-427. (2009) Zbl1224.05465MR2501981
  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. (2017) MR3702241
  11. Zhang, X., Vertex splitting for determining the f -chromatic class of simple graphs, Submitted. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.