Search

Given a simple directed graph D = (V,A), let the size of the largest induced acyclic subgraph (dag) of D be denoted by mas(D). Let D ∈ D(n, p) be a random instance, obtained by choosing each of the (2n) possible undirected edges independently with probability 2p and then orienting each chosen edge independently in one of two possible directions with probability 1/2. We obtain improved bounds on the range of concentration, upper and lower bounds of mas(D). Our main result is that mas(D) ≥ [2 logq np - X], where q = (1 - p)-1, X = 1 if p ≥ n-1/3+∈ (∈ > 0 is any constant), X = W/(ln q) if p ≥ C/n, whereW >4 is any constant (and C = C(W) is a suitably large constant). This improves the previously known lower bounds of [J. Spencer and C. Subramanian, Discrete Math. Theor. Comput. Sci., 10 (2008); C. R. Subramanian, Electron. J. Combin., 10 (2003)], where there is an O(ln ln np/ ln q) term instead of X. We also obtain a slight improvement on the upper bound, using an upper bound on the number of acyclic orientations of an undirected graph. Limitations on further improvements on the upper bound (using first moment arguments) are also established. We also analyze a polynomial-time heuristic to find a large induced dag and show that it produces a solution whose size is at least logq np+Θ(√logq np). Our results also carry over to a related model D2(n, p) in which each possible directed arc is chosen independently with probability p. [ABSTRACT FROM AUTHOR]

Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from G(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b* or b* + 1, where b* = ⎣2(logr n) + 0.5⎦ and r = p-1. It is also shown that if, asymptotically, 2(logr n) + 1 is not within a distance of w(n)/(ln n) (for any sufficiently slow w(n) →∞) from an integer, then mat(D) is ⎣ 2(logr n) + 1⎦ a.a.s. As a consequence, it is shown that mat(D) is 1-point concentrated for all n belonging to a subset of positive integers of density 1 if p is independent of n. It is also shown that there are functions p = p(n) for which mat(D) is provably not concentrated in a single value. We also establish thresholds (on p) for the existence of induced acyclic tournaments of size i which are sharp for i = i(n) →∞. We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least logr n + Θ(√logr n). Our results are valid as long as p ≥ 1/n. All of these results also carry over (with some slight changes) to a related model which allows 2-cycles. [ABSTRACT FROM AUTHOR]

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs. [ABSTRACT FROM AUTHOR]

We propose the following problem. For some k ⩾ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ′k(G). Let fk be defined by fk(Δ) = (These character(s) cannot be represented in ASCII text). We show that (These character(s) cannot be represented in ASCII text). We also discuss some open problems. [ABSTRACT FROM AUTHOR]