Sum coloring and interval graphs: A tight upper bound for the minimum number of colors
From MaRDI portal
Publication:1827686
DOI10.1016/J.DISC.2003.06.015zbMATH Open1041.05030OpenAlexW2000545501MaRDI QIDQ1827686FDOQ1827686
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
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
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?)
- 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
- Title not available (Why is that?)
- 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 (7)
- Minimum sum coloring problem: upper bounds for the chromatic strength
- A matched approximation bound for the sum of a greedy coloring
- 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
- Sum coloring on certain classes of graphs
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)
