- Tytuł:
- On the cost chromatic number of outerplanar, planar, and line graphs
- Autorzy:
-
Mitchem, John
Morriss, Patrick
Schmeichel, Edward - Powiązania:
- https://bibliotekanauki.pl/articles/971958.pdf
- Data publikacji:
- 1997
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
cost coloring
outerplanar
planar
line graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 229-241
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł