On the cost chromatic number of outerplanar, planar, and line graphs
John Mitchem, Patrick Morriss, Edward Schmeichel (1997)
Discussiones Mathematicae Graph Theory
Similarity:
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...