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

DOI10.1016/j.disc.2003.06.015zbMath1041.05030OpenAlexW2000545501MaRDI QIDQ1827686

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

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

Related Items (4)

The interval-merging problem ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Minimum sum edge colorings of multicycles ⋮ A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph

Cites Work

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

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