The Balanced Decomposition Number of TK4 and Series-Parallel Graphs
A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G)...
The B-Domatic Number of a Graph
Besides the classical chromatic and achromatic numbers of a graph related to minimum or minimal vertex partitions into independent sets, the b-chromatic number was introduced in 1998 thanks to an alternative definition of the minimality of such partitions. When independent sets are replaced by dominating sets, the parameters corresponding to the chromatic and achromatic numbers are the domatic and adomatic numbers d(G) and ad(G). We introduce the b-domatic number bd(G) as the counterpart of the...
The bigraph decomposition number of a graph
The bipartite Ramsey numbers.
The Chvátal-Erdős condition and 2-factors with a specified number of components
Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components,...
The decomposability of additive hereditary properties of graphs
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that , the subgraph of G induced by , is in , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂....
The directed anti-Oberwolfach solution: Pancyclic 2-factorizations of complete directed graphs of odd order.
The edge domination problem
An edge dominating set of a graph is a set D of edges such that every edge not in D is adjacent to at least one edge in D. In this paper we present a linear time algorithm for finding a minimum edge dominating set of a block graph.
The Edmonds-Gallai decomposition for the -piece packing problem.
The excessive [3]-index of all graphs.
The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks
It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another...
The fundamental group and Galois coverings of hexagonal systems in 3-space.
The higher-order matching polynomial of a graph.
The -tuple domatic number of a graph
The linear arboricity of -regular graphs
The list linear arboricity of planar graphs
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9.
The matching polynomial of a distance-regular graph.
The maximum genus, matchings and the cycle space of a graph
In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .
The maximum number of perfect matchings in graphs with a given degree sequence.