๐ฎ
๐ฎ
The Ethereal
Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees
September 14, 2017 ยท The Ethereal ยท ๐ Theoretical Computer Science
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal