HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees

Cédric Bentz 1
1 CEDRIC - OC - CEDRIC. Optimisation Combinatoire
CEDRIC - Centre d'études et de recherche en informatique et communications
Abstract : For a fixed number of colors, we show that, in node-weighted split graphs, cographs, and graphs of bounded tree-width, one can determine in polynomial time whether a proper list-coloring of the vertices of a graph such that the total weight of vertices of each color equals a given value in each part of a fixed partition of the vertices exists. We also show that this result is tight in some sense, by providing hardness results for the cases where any one of the assumptions does not hold. The edge-coloring variant is also studied, as well as special cases of cographs and split graphs.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal-cnam.archives-ouvertes.fr/hal-02444296
Contributor : Cédric Bentz Connect in order to contact the contributor
Submitted on : Monday, January 20, 2020 - 3:52:47 PM
Last modification on : Monday, February 21, 2022 - 3:38:20 PM
Long-term archiving on: : Tuesday, April 21, 2020 - 6:26:02 PM

File

1709.05000.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Cédric Bentz. Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees. Theoretical Computer Science, Elsevier, 2019, 782, pp.11-29. ⟨10.1016/j.tcs.2019.02.029⟩. ⟨hal-02444296⟩

Share

Metrics

Record views

47

Files downloads

78