On the cost chromatic number of outerplanar, planar, and line graphs
Discussiones Mathematicae Graph Theory, Tome 17 (1997) no. 2, p. 229.

Voir la notice de l'article dans European Digital Mathematics Library

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.
Classification : 05C10, 05C15
Mots-clés : cost coloring, outerplanar, planar, line graphs, maximal outerplanar and maximal planar graphs 
@article{DMGT_1997__17_2_270344,
     author = {John Mitchem and Patrick Morriss and Edward Schmeichel},
     title = {On the cost chromatic number of outerplanar, planar, and line graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {229},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {1997},
     zbl = {0909.05027},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_1997__17_2_270344/}
}
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
SP  - 229
VL  - 17
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_1997__17_2_270344/
LA  - en
ID  - DMGT_1997__17_2_270344
ER  - 
%0 Journal Article
%A John Mitchem
%A Patrick Morriss
%A Edward Schmeichel
%T On the cost chromatic number of outerplanar, planar, and line graphs
%J Discussiones Mathematicae Graph Theory
%D 1997
%P 229
%V 17
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_1997__17_2_270344/
%G en
%F DMGT_1997__17_2_270344
John Mitchem; Patrick Morriss; Edward Schmeichel. On the cost chromatic number of outerplanar, planar, and line graphs. Discussiones Mathematicae Graph Theory, Tome 17 (1997) no. 2, p. 229. https://geodesic-test.mathdoc.fr/item/DMGT_1997__17_2_270344/