On the minimum sum coloring of \(P_4\)-sparse graphs

DOI10.1007/s00373-012-1269-5zbMath1298.05106OpenAlexW2020658670MaRDI QIDQ742570

Mario Valencia-Pabon, Flavia Bonomo-Braberman

Publication date: 19 September 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-012-1269-5

zbMATH Keywords

graph coloring\(P_4\)-sparse graphsminimum sum coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)

Related Items (3)

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs

Cites Work

• Unnamed Item
• A Helly theorem for convexity in graphs
• A tree representation for \(P_ 4\)-sparse graphs
• On the sum coloring problem on interval graphs
• On chromatic sums and distributed resource allocation
• On sum coloring of graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Approximating min sum set cover
• Minimum Sum Coloring of P4-sparse graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Minimum Color Sum of Bipartite Graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Approximation results for the optimum cost chromatic partition problem

This page was built for publication: On the minimum sum coloring of \(P_4\)-sparse graphs