Equitable d-degenerate choosability of graphs

DOI10.1007/978-3-030-48966-3_19arXiv2003.09722MaRDI QIDQ6337166FDOQ6337166

Elżbieta Sidorowicz, Ewa Drgas-Burchardt, Hanna Furmańczyk

Publication date: 21 March 2020

Abstract: Let ${mathcalD}_d$ be the class of $d$-degenerate graphs and let $L$ be a list assignment for a graph $G$. A colouring of $G$ such that every vertex receives a colour from its list and the subgraph induced by vertices coloured with one color is a $d$-degenerate graph is called the $(L,{mathcalD}_d)$-colouring of $G$. For a $k$-uniform list assignment $L$ and $dinmathbb{N}_0$, a graph $G$ is equitably $(L,{mathcalD}_d)$-colorable if there is an $(L,{mathcalD}_d)$-colouring of $G$ such that the size of any colour class does not exceed $leftlceil|V(G)|/kightceil$. An equitable $(L,{mathcalD}_d)$-colouring is a generalization of an equitable list coloring, introduced by Kostochka at al., and an equitable list arboricity presented by Zhang. Such a model can be useful in the network decomposition where some structural properties on subnets are imposed. In this paper we give a polynomial-time algorithm that for a given $(k,d)$-partition of $G$ with a $t$-uniform list assignment $L$ and $tgeqk$, returns its equitable $(L,mathcal{D}_{d-1})$-colouring. In addition, we show that 3-dimensional grids are equitably $(L,mathcal{D}_1)$-colorable for any $t$-uniform list assignment $L$ where $tgeq3$.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

This page was built for publication: Equitable $d$-degenerate choosability of graphs

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