401. On Equitable Colorings of Sparse Graphs
- Author
-
Xin Zhang
- Subjects
Discrete mathematics ,Vertex (graph theory) ,Conjecture ,Degree (graph theory) ,General Mathematics ,010102 general mathematics ,Complete graph ,0102 computer and information sciences ,01 natural sciences ,1-planar graph ,Complete bipartite graph ,Combinatorics ,010201 computation theory & mathematics ,Equitable coloring ,0101 mathematics ,Connectivity ,Mathematics - Abstract
A graph is equitably k-colorable if G has a proper vertex k-coloring such that the sizes of any two color classes differ by at most one. Chen, Lih and Wu conjectured that any connected graph G with maximum degree $$\Delta $$ distinct from the odd cycle, the complete graph $$K_{\Delta +1}$$ and the complete bipartite graph $$K_{\Delta ,\Delta }$$ are equitably m-colorable for every $$m\ge \Delta $$ . Let $${\mathcal {G}}_k$$ be the class of graphs G such that $$e(G')\le k (v(G')-2)$$ for every subgraph $$G'$$ of G with order at least 3. In this paper, it is proved that any graph in $${\mathcal {G}}_4$$ with maximum degree $$\Delta \ge 17$$ is equitably m-colorable for every $$m\ge \Delta $$ . As corollaries, we confirm Chen–Lih–Wu Conjecture for 1-planar graphs, 3-degenerate graphs and graphs with maximum average degree less than 6, provided that $$\Delta \ge 17$$ .
- Published
- 2015