Minimum sum coloring of P₄-sparse graphs

DOI10.1016/J.ENDM.2009.11.048MaRDI QIDQ2840552zbMATH OpenOpenAlexFDO

Authors Mario Valencia-Pabon, Flavia Bonomo

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

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

Recommendations

• On the minimum sum coloring of P₄-sparse graphs
• Lower bounds for the minimal sum coloring problem
• New variable neighborhood search method for minimum sum coloring problem on simple graphs
• New algorithm for the sum coloring problem
• A memetic algorithm for the minimum sum coloring problem

Cites work

• scientific article; zbMATH DE number 1947053 (Why is no real title available?)
• A tree representation for \(P_ 4\)-sparse graphs
• Approximating min sum set cover
• Approximation results for the optimum cost chromatic partition problem
• Minimum Color Sum of Bipartite Graphs
• On chromatic sums and distributed resource allocation
• On sum coloring of graphs
• On the sum coloring problem on interval graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is \cal NP-Complete
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• The chromatic sum of a graph: history and recent developments

Cited in

(8)

• Computing lower bounds for minimum sum coloring and optimum cost chromatic partition
• 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
• The packing coloring problem for lobsters and partner limited graphs
• On the minimum sum coloring of P₄-sparse graphs
• Minimum sum set coloring of trees and line graphs of trees
• Minimal separators in \(P_4\)-sparse graphs
• An exact algorithm for the minimum sum coloring problem on partially decomposable graphs

This page was built for publication: Minimum sum coloring of \(P_{4}\)-sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840552)