A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal...
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization...
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...
The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal...
A -ranking of a graph is a mapping such that each path with endvertices of the same colour contains an internal vertex with colour greater than . The ranking number of a graph is the smallest positive integer admitting a -ranking of . In the on-line version of the problem, the vertices of arrive one by one in an arbitrary order, and only the edges of the induced graph are known when the colour for the vertex has to be chosen. The on-line ranking number of a graph is the smallest...
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P...
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.
A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph...
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...
Download Results (CSV)