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

September 14, 2017 ยท The Ethereal ยท ๐Ÿ› Theoretical Computer Science

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Cรฉdric Bentz arXiv ID 1709.05000 Category cs.DM: Discrete Mathematics Cross-listed cs.DS Citations 3 Venue Theoretical Computer Science Last Checked 2 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Discrete Mathematics