The cost chromatic number and hypergraph parameters
Discussiones Mathematicae Graph Theory (2006)
- Volume: 26, Issue: 3, page 369-376
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topGá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] 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] 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] 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] E. Kubicka, Constraints on the chromatic sequence for trees and graphs, Congr. Numer. 76 (1990) 219-230. Zbl0862.05044
- [5] E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in: Proc. ACM Computer Science Conference, Louisville (Kentucky) 1989, 39-45.
- [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] 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] M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method (Springer, 2002). Zbl0987.05002
- [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] Zs. Tuza, Contractions and minimal k-colorability, Graphs and Combinatorics 6 (1990) 51-59, doi: 10.1007/BF01787480.
- [11] Zs. Tuza, Problems and results on graph and hypergraph colorings, Le Matematiche 45 (1990) 219-238.
NotesEmbed ?
topYou 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.