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

DOI10.1016/J.DISC.2003.06.015zbMATH Open1041.05030OpenAlexW2000545501MaRDI QIDQ1827686FDOQ1827686

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Smallest-last ordering and clustering and graph coloring algorithms
• On a graph partition problem with application to VLSI layout
• On chromatic number of graphs and set-systems
• An inequality for the chromatic number of a graph
• The chromatic sum of a graph: history and recent developments
• Coloring of trees with minimum sum of colors
• Contractions and minimal k-colorability
• On the sum coloring problem on interval 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
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• The color cost of a caterpillar
• On the cost-chromatic number of graphs
• Minimal coloring and strength of graphs
• Tabular graphs and chromatic sum

Cited In (5)

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

Recommendations

• Title not available (Why is that?) 👍 👎
• Lower bounds for the minimal sum coloring problem 👍 👎
• An upper bound for total colouring of graphs 👍 👎
• Total colorings of graphs with minimum sum of colors 👍 👎
• On the sum coloring problem on interval graphs 👍 👎
• On sum coloring of graphs 👍 👎
• A short proof of the NP-completeness of minimum sum interval coloring 👍 👎
• Tight bounds on the chromatic sum of a connected graph 👍 👎
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs 👍 👎
• Minimum sum coloring problem: upper bounds for the chromatic strength 👍 👎

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)