Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cost coloring

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

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

100%

Mitchem J., Morriss P., Schmeichel E.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 2

229-241

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.

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

88%

Giaro K., Kubale M.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 2

361-376

We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Giaro K.

1 Kubale M.

1 Mitchem J.

1 Morriss P.

1 Schmeichel E.

1 2009

1 1997

Wyniki wyszukiwania

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

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs