Minimum Sum Coloring of P4-sparse graphs

DOI10.1016/j.endm.2009.11.048zbMath1268.05063OpenAlexW2091005072MaRDI QIDQ2840552

Mario Valencia-Pabon, Flavia Bonomo-Braberman

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringminimum sum coloring\(P_{4}\)-sparse graphsmaximal sequence

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ The packing coloring problem for lobsters and partner limited graphs ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ 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 tree representation for \(P_ 4\)-sparse graphs
• On the sum coloring problem on interval graphs
• On chromatic sums and distributed resource allocation
• The chromatic sum of a graph: history and recent developments
• On sum coloring of graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Approximating min sum set cover
• 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: Minimum Sum Coloring of P4-sparse graphs