On domatic numbers of graphs
On edge independence numbers and edge covering numbers of -uniform hypergraph
On -domination number of a graph
On Fulkerson conjecture
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover,...
On generalized list colourings of graphs
Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (𝓟,k)-choosability have been proved. In this paper we prove some extensions of the well-known bounds for...
On generating sets of induced-hereditary properties
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...
On Graphs with Disjoint Dominating and 2-Dominating Sets
A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the...
On hypergraph coverings
On independent vertices and edges of belt graphs.
On isopart parameters of complete bipartite graphs and -cubes
On -domatic numbers of graphs
On k-factor-critical graphs
A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.
On maximal matchings in and a conjecture of R. Forcade
On normal partitions in cubic graphs
A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.
On number of covering arcs in orderings
On odd and semi-odd linear partitions of cubic graphs
A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition is said to be odd whenever each path of has odd length and semi-odd whenever each path of (or each path of ) has odd length. In [2] Aldred...
On P4-tidy graphs.
On perfect and unique maximum independent sets in graphs
A perfect independent set of a graph is defined to be an independent set with the property that any vertex not in has at least two neighbors in . For a nonnegative integer , a subset of the vertex set of a graph is said to be -independent, if is independent and every independent subset of with is a subset of . A set of vertices of is a super -independent set of if is -independent in the graph , where is the bipartite graph obtained from by deleting all edges...
On permutations in bipartite graphs
On -extendability of the hypercube
A graph having a perfect matching is called -extendable if every matching of size can be extended to a perfect matching. It is proved that in the hypercube , a matching with can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, is -extendable for every with