Equitable choosability of prism graphs
The list colouring problem of a graph \(G\) is now quite a well-known problem. Every vertex \(v\) in \(V(G)\) is assigned a list \(L(v)\) of \(k\)-colours, and if, for every such list assignment of \(L\) to \(V(G)\), there is proper colouring of \(G\) in which every vertex \(v\) is coloured with a colour from \(L(v)\), then \(G\) is said to be \(k\)-choosable. In this paper, the authors consider a variant of this problem introduced by \textit{A. V. Kostochka} et al. [J. Graph Theory 44, No. 3, 166--177 (2003; Zbl 1031.05050)]. A graph is said to be equitably \(k\)-choosable if \(G\) is \(k\)-choosable in such a way that the size of each colour class is bounded above by \(\lceil |V(G)|/k\rceil\). Kostochka et al. [loc. cit.] conjectured that, if \(\Delta(G)\geq3\) is the maximum degree of \(G\), then \(G\) is equitably \(\Delta(G)\)-choosable as long as \(G\) is not complete or \(K_{d,d}\) for odd \(d\).\N\NIn this paper, using a discharging argument, it is shown that the \(n\)-prism, which is the Cartesian product \(C_n\Box K_2\) where \(C_n\) is the \(n\)-cycle with \(n\geq3\), is equitably 3-choosable.
- A list analogue of equitable coloring
- Equitable and equitable list colorings of graphs
- Equitable coloring and equitable choosability of graphs with small maximum average degree
- Equitable coloring and the maximum degree
- Equitable list coloring of graphs
- Equitable list-coloring for graphs of maximum degree 3
- Graph theory
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
This page was built for publication: Equitable choosability of prism graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6982910)
