The cost chromatic number and hypergraph parameters

Gábor Bacsó; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 3, page 369-376
  • ISSN: 2083-5892

Abstract

top
In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.

How to cite

top

Gábor Bacsó, and Zsolt Tuza. "The cost chromatic number and hypergraph parameters." Discussiones Mathematicae Graph Theory 26.3 (2006): 369-376. <http://eudml.org/doc/270537>.

@article{GáborBacsó2006,
abstract = {In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.},
author = {Gábor Bacsó, Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph coloring; cost chromatic number; intersection number of a hypergraph; graph colorings; intersection number of hypergraphs},
language = {eng},
number = {3},
pages = {369-376},
title = {The cost chromatic number and hypergraph parameters},
url = {http://eudml.org/doc/270537},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Gábor Bacsó
AU - Zsolt Tuza
TI - The cost chromatic number and hypergraph parameters
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 3
SP - 369
EP - 376
AB - In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
LA - eng
KW - graph coloring; cost chromatic number; intersection number of a hypergraph; graph colorings; intersection number of hypergraphs
UR - http://eudml.org/doc/270537
ER -

References

top
  1. [1] Y. Alavi, P. Erdős, P.J. Malde, A.J. Schwenk and C. Thomassen, Tight bounds on the chromatic sum of a connected graph, J. Graph Theory 13 (1989) 353-357, doi: 10.1002/jgt.3190130310. Zbl0677.05028
  2. [2] U. Feigle, L. Lovász and P. Tetali, Approximating sum set cover, Algorithmica 40 (2004) 219-234, doi: 10.1007/s00453-004-1110-5. Zbl1082.68126
  3. [3] M. Gionfriddo, F. Harary and Zs. Tuza, The color cost of a caterpillar, Discrete Math. 174 (1997) 125-130, doi: 10.1016/S0012-365X(96)00325-1. Zbl0887.05018
  4. [4] E. Kubicka, Constraints on the chromatic sequence for trees and graphs, Congr. Numer. 76 (1990) 219-230. Zbl0862.05044
  5. [5] E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in: Proc. ACM Computer Science Conference, Louisville (Kentucky) 1989, 39-45. 
  6. [6] J. Mitchem and P. Morriss, On the cost chromatic number of graphs, Discrete Math. 171 (1997) 201-211, doi: 10.1016/S0012-365X(96)00005-2. Zbl0876.05031
  7. [7] J. Mitchem, P. Morriss and E. Schmeichel, On the cost chromatic number of outerplanar, planar and line graphs, Discuss. Math. Graph Theory 17 (1997) 229-241, doi: 10.7151/dmgt.1050. Zbl0909.05027
  8. [8] M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method (Springer, 2002). Zbl0987.05002
  9. [9] T. Szkaliczki, Routing with minimum wire length in the Dogleg-free Manhattan Model, SIAM Journal on Computing 29 (1999) 274-287, doi: 10.1137/S0097539796303123. Zbl0937.68055
  10. [10] Zs. Tuza, Contractions and minimal k-colorability, Graphs and Combinatorics 6 (1990) 51-59, doi: 10.1007/BF01787480. 
  11. [11] Zs. Tuza, Problems and results on graph and hypergraph colorings, Le Matematiche 45 (1990) 219-238. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.