Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

Partial covers of graphs

Jirí FialaJan Kratochvíl — 2002

Discussiones Mathematicae Graph Theory

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...

Graphs maximal with respect to hom-properties

Jan KratochvílPeter MihókGabriel Semanišin — 1997

Discussiones Mathematicae Graph Theory

For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.

Page 1

Download Results (CSV)