Maximum colorful independent sets in vertex-colored graphs

DOI10.1016/j.endm.2018.06.043zbMath1397.05132OpenAlexW2883535968MaRDI QIDQ1792109

Yannis Manoussakis, Hong Phong Pham

Publication date: 11 October 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2018.06.043

zbMATH Keywords

polynomial-time algorithmsvertex-colored graphsmaximum colorful independent sets

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On the \(k\)-colored rainbow sets in fixed dimensions

Cites Work

• Unnamed Item
• Colorful paths in vertex coloring of graphs
• Decomposition by clique separators
• Tropical dominating sets in vertex-coloured graphs
• Tropical matchings in vertex-colored graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Paths, Trees, and Flowers
• Independent Set in P₅-Free Graphs in Polynomial Time