Sum coloring and interval graphs: A tight upper bound for the minimum number of colors

DOI10.1016/J.DISC.2003.06.015MaRDI QIDQ1827686zbMATH OpenOpenAlexFDO

Authors Sara Nicoloso

Publication date 6 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.06.015

zbMATH Keywords

ColoringUpper boundInterval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the sum coloring problem on interval graphs
• Minimum sum coloring problem: upper bounds for the chromatic strength
• A short proof of the NP-completeness of minimum sum interval coloring
• Total colorings of graphs with minimum sum of colors
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
• Lower bounds for the minimal sum coloring problem
• On sum coloring of graphs
• Sum coloring on certain classes of graphs
• Tight bounds on the chromatic sum of a connected graph
• An upper bound for total colouring of graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4154469 (Why is no real title available?)
• An inequality for the chromatic number of a graph
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Approximation results for the optimum cost chromatic partition problem
• Coloring of trees with minimum sum of colors
• Contractions and minimal k-colorability
• Minimal coloring and strength of graphs
• On a graph partition problem with application to VLSI layout
• On chromatic number of graphs and set-systems
• On the cost-chromatic number of graphs
• On the sum coloring problem on interval graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Smallest-last ordering and clustering and graph coloring algorithms
• Tabular graphs and chromatic sum
• The chromatic sum of a graph: history and recent developments
• The color cost of a caterpillar

Cited in

(7)

• Sum coloring on certain classes of graphs
• Minimum sum coloring problem: upper bounds for the chromatic strength
• A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph
• The interval-merging problem
• A short proof of the NP-completeness of minimum sum interval coloring
• Minimum sum edge colorings of multicycles
• A matched approximation bound for the sum of a greedy coloring

This page was built for publication: Sum coloring and interval graphs: A tight upper bound for the minimum number of colors

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