On $g_c$-colorings of nearly bipartite graphs

Zhang, Yuzhuo ; Zhang, Xia

Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 433-444.

Résumé

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.

Détail

DOI : 10.21136/CMJ.2018.0477-16

Classification : 05C15
Keywords: edge coloring; nearly bipartite graph; edge covering coloring; $g_c$-coloring; edge cover decomposition