Article in press
Authors:
Title:
Equitable cluster partition of graphs with small maximum average degree
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-12-04 , Revised: 2024-09-30 , Accepted: 2024-09-30 , Available online: 2024-10-09 , https://doi.org/10.7151/dmgt.2564
Abstract:
An equitable $\underbrace{({\mathcal{O}}_{k}, {\mathcal{O}}_{k}, \ldots,
{\mathcal{O}}_{k})}_m$-partition of a graph $G$, which is also called an
equitable $k$ cluster $m$-partition, is the partition of $V(G)$ into $m$
non-empty subsets $V_{1}$, $V_{2}$, \ldots, $V_{m}$ such that for every integer
$i$ in $\{1, 2, \ldots, m\}$, $G[V_{i}]$ is a graph with components of order at
most $k$, and for each pair of distinct $i, j$ in $\{1,\ldots, m\}$, there is
$-1\leq|V_{i}|-|V_{j}|\leq1$. In this paper, we proved that every graph $G$
with minimum degree $\delta(G)\geq2$ and maximum average degree
$mad(G)<\frac{8}{3}$ admits an equitable $\underbrace{({\mathcal{O}}_{6},
{\mathcal{O}}_{6}, \ldots, {\mathcal{O}}_{6})}_m$-partition, for any integer
$m\geq3$.
Keywords:
equitable cluster partition, maximum average degree, discharging
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, Amsterdam, 1976).
- B.-L. Chen, K.-W. Lih and P.-L. Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443–447.
https://doi.org/10.1006/eujc.1994.1047 - A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, in: Combinatorial Theory and Its Applications, P. Erdős, A. Rényi and V.T. Sós (Ed(s)), (North-Holland, Amsterdam 1970) 601–623.
- M. Li and X. Zhang, Relaxed equitable colorings of planar graphs with girth at least $8$, Discrete Math. 343 (2020) 111790.
https://doi.org/10.1016/j.disc.2019.111790 - R. Luo, J.S. Sereni, D.C. Stephens and G.X. Yu, Equitable coloring of sparse planar graphs, SIAM J. Discrete Math. 24 (2010) 1572–1583.
https://doi.org/10.1137/090751803 - L. Williams, J. Vandenbussche and G.X. Yu, Equitable defective coloring of sparse planar graphs, Discrete Math. 312 (2012) 957–962.
https://doi.org/10.1016/j.disc.2011.10.024 - J.L. Wu and P. Wang, Equitable coloring planar graphs with large girth, Discrete Math. 308 (2008) 985–990.
https://doi.org/10.1016/j.disc.2007.08.059 - Y. Zhang and H.P. Yap, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998) 97–105.
Close