Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Partial covers of graphs

100%

Fiala J., Kratochvíl J.

Discussiones Mathematicae Graph Theory

2002

tom 22

nr 1

89-99

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of deciding existence of partial covers and of full covers (locally bijective homomorphisms), which were previously studied.

New lower bounds on the weighted chromatic number of a graph

100%

Caramia M., Fiala J.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 2

183-195

In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Fiala J.

1 Caramia M.

1 Kratochvíl J.

1 2004

1 2002

Wyniki wyszukiwania

Partial covers of graphs

New lower bounds on the weighted chromatic number of a graph