2020/03/21 by Ewa Drgas‐Burchardt, Drgas-Burchardt, E., Hanna Furmańczyk +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2003.09722
openalex publication_date 2020/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \mathcal Dd 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,\mathcal Dd)-colouring of G. For a k-uniform list assignment L and d∈ℕ0, a graph G is equitably (L,\mathcal Dd)-colorable if there is an (L,\mathcal Dd)-colouring of G such that the size of any colour class does not exceed \lceil|V(G)|/k\rceil. An equitable (L,\mathcal Dd)-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 t≥ k, returns its equitable (L,Dd-1)-colouring. In addition, we show that 3-dimensional grids are equitably (L,D1)-colorable for any t-uniform list assignment L where t≥ 3.