We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.
Suppose a graph whose edges are partitioned into disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number of categories and present some polynomial algorithm.
We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].
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 recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices and five edges . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from...
The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this...
Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → -1,1 satisfying for every v ∈ V(G), where . The maximum of the values of , taken over all signed matchings x, is called the signed matching number and is denoted by β’₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β’₁(G) for general graphs....