On the cost chromatic number of outerplanar, planar, and line graphs

John Mitchem; Patrick Morriss; Edward Schmeichel

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 2, page 229-241
  • ISSN: 2083-5892

Abstract

top
We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct several infinite classes of counterexamples to a conjecture of Harary and Plantholt on the cost chromatic number of line graphs.

How to cite

top

John Mitchem, Patrick Morriss, and Edward Schmeichel. "On the cost chromatic number of outerplanar, planar, and line graphs." Discussiones Mathematicae Graph Theory 17.2 (1997): 229-241. <http://eudml.org/doc/270344>.

@article{JohnMitchem1997,
abstract = {We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct several infinite classes of counterexamples to a conjecture of Harary and Plantholt on the cost chromatic number of line graphs.},
author = {John Mitchem, Patrick Morriss, Edward Schmeichel},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cost coloring; outerplanar; planar; line graphs; maximal outerplanar and maximal planar graphs},
language = {eng},
number = {2},
pages = {229-241},
title = {On the cost chromatic number of outerplanar, planar, and line graphs},
url = {http://eudml.org/doc/270344},
volume = {17},
year = {1997},
}

TY - JOUR
AU - John Mitchem
AU - Patrick Morriss
AU - Edward Schmeichel
TI - On the cost chromatic number of outerplanar, planar, and line graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 2
SP - 229
EP - 241
AB - We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct several infinite classes of counterexamples to a conjecture of Harary and Plantholt on the cost chromatic number of line graphs.
LA - eng
KW - cost coloring; outerplanar; planar; line graphs; maximal outerplanar and maximal planar graphs
UR - http://eudml.org/doc/270344
ER -

References

top
  1. [1] P. Erdős, E. Kubicka and A. Schwenk, Graphs that Require Many Colors to Achieve Their Chromatic Sum, Congressus Numerantium 71 (1990) 17-28. Zbl0704.05020
  2. [2] S. Fiorini and R.J. Wilson, Edge-colorings of Graphs (Pitman, 1977). Zbl0421.05023
  3. [3] M. Gionfriddo, F. Harary and Zs. Tuza, The Color Cost of a Caterpillar, Discrete Mathematics, to appear. 
  4. [4] H. Izbicki, Zulässige Kantenfärbungen von Pseudo-Regulären Graphen mit Minimaler Kantenfarbenzahl, Monatsh. Math. 67 (1963) 25-31, doi: 10.1007/BF01300678. Zbl0113.17405
  5. [5] E. Kubicka, The Chromatic Sum of a Graph (Ph.D. Dissertation, Western Michigan University, 1989). Zbl1064.05062
  6. [6] E. Kubicka, Constraints on the Chromatic Sequence for Trees and Graphs, Congressus Numerantium 76 (1990) 219-230. Zbl0862.05044
  7. [7] E. Kubicka, G. Kubicka and D. Kountanis, Approximation Algorithms for the Chromatic Sum, in: Proceedings 1st Great Lakes Computer Science Conference, Michigan, October 1989 (Springer-Verlag LNCS 507, 15-21). 
  8. [8] E. Kubicka and A.J. Schwenk, An Introduction to Chromatic Sum, in: Proceedings 17th ACM Computer Science Conference 1989, 39-45. 
  9. [9] J. Mitchem and P. Morriss, On the Cost-Chromatic Number of Graphs, Discrete Mathematics 171 (1997) 201-211, doi: 10.1016/S0012-365X(96)00005-2. Zbl0876.05031
  10. [10] S. Nicoloso, M. Sarrafzadeh and X. Song, On the Sum Coloring Problem on Interval Graphs, Consiglió Nazionale Delle Ricerche, Instituto Di Analisi Dei Sistemi Ed Informatica, October 1994. 
  11. [11] K. Supowit, Finding a Maximum Planar Subset of a Set of Nets in a Channel, IEEE Transactions on Computer Aided Design, CAD-6 1 (1987) 93-94. 
  12. [12] C. Thomassen, P. Erdős, Y. Alavi, P.J. Malde and A.J. Schwenk, Tight Bounds on the Chromatic Sum of a Connected Graph, Journal of Graph Theory 13 (1989) 353-357, doi: 10.1002/jgt.3190130310. Zbl0677.05028
  13. [13] Zs. Tuza, Contractions and Minimal k-Colorability, Graphs and Combinatorics 6 (1990) 51-59, doi: 10.1007/BF01787480. Zbl0704.05017
  14. [14] Zs. Tuza, Problems and Results on Graph and Hypergraph Colorings, Le Matematiche 45 (1990) 219-238. Zbl0735.05041
  15. [15] Zs. Tuza, Chromatic Numbers and Orientations, February, 1993, unpublished manuscript. 
  16. [16] V.G. Vizing, On an Extimate of the Chromatic Class of a p-Graph, Diskret. Analiz 3 (1964) 25-30. 
  17. [17] D. West, Open Problems Section, The Siam Activity Group on Discrete Mathematics Newsletter 5 (2) (Winter 1994-95) 9. 

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.