On the Equitable Choosability of the Disjoint Union of Stars

DOI10.1007/S00373-022-02571-2MaRDI QIDQ6347089arXivFDO

Authors Hemanshu Kaul, J. A. Mudrock, Tim Wagstrom

Publication date 12 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00373-022-02571-2

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

arXiv classification

math.CO

Abstract: Equitable $k$-choosability is a list analogue of equitable $k$-coloring that was introduced by Kostochka, Pelsmajer, and West in 2003. It is known that if vertex disjoint graphs $G_1$ and $G_2$ are equitably $k$-choosable, the disjoint union of $G_1$ and $G_2$ may not be equitably $k$-choosable. Given any $minmathbbN$ the values of $k$ for which $K_{1,m}$ is equitably $k$-choosable are known. Also, a complete characterization of equitably $2$-choosable graphs is not known. With these facts in mind, we study the equitable choosability of $su{m}_{i=1}^n{K}_{1,m_i}$, the disjoint union of $n$ stars. We show that determining whether $su{m}_{i=1}^n{K}_{1,m_i}$ is equitably choosable is NP-complete when the same list of two colors is assigned to every vertex. We completely determine when the disjoint union of two stars (or $ngeq2$ identical stars) is equitably 2-choosable, and we present results on the equitable $k$-choosability of the disjoint union of two stars for arbitrary $k$.

This page was built for publication: On the Equitable Choosability of the Disjoint Union of Stars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347089)