ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 17(2) (1997)
Department of Mathematics & Computer Science
San Jose State University, San Jose, California 95192
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.
Keywords: cost coloring, outerplanar, planar, line graphs.
1991 Mathematics Subject Classification: Primary 05C15, Secondary 05C10.