Abstract. The concentration of the sizes of largest induced paths and cycles (holes) is studied in Erdős–Rényi random graphs. A 2-point concentration is proved for the size of the largest induced path and cycle for all [Formula: see text] satisfying [Formula: see text] and [Formula: see text] where [Formula: see text] is any constant. No such tight concentration (within two consecutive values) was previously known for induced paths and cycles. As a corollary, a significant additive improvement is obtained over a 40-year-old result of Erdős and Palka [ Discrete Math., 46 (1983), pp. 145–150] concerning the size of the largest induced tree in a dense random graph. Further, the induced path decomposition number and induced tree decomposition number, i.e., the smallest number of parts into which the vertex set of a graph can be partitioned such that every part induces a (i) path or (ii) tree, respectively, are studied for [Formula: see text]. The arguments involve the second moment method together with an adaptation of a martingale-based technique of Krivelevich et al. [ Random Structures Algorithms, 22 (2003), pp. 1–14] for monotone high-degree polynomial random variables to the nonmonotone setting. A lower bound is proved showing the tightness of the application of the inequality up to logarithmic factors in the exponent. The modified inequality is then stated and proved in a general setting, which may be of independent interest.

Buffer capacities at routers are ever-increasing to accommodate the extreme-scale increase in the volume of incoming traffic. Sophisticated packet classification is being adopted to address challenges in meeting application demands. With the number of rules for classification and packets arriving at routers per second reaching 100's of thousands to millions, special hardware is also being built for packet classification to increase throughput at routers. Sorting packets (based on various conditions) in the buffers offers a significant advantage for the packet classification process. The sorting step is a time-consuming step given the large volume of packets in the incoming buffers. We propose a technique to approximately sort the packets by capping the maximum number of comparisons that can be made. We show that the performance of well-known decision tree-based packet classification methods such as HyperCuts, EffiCuts, and SmartSplits can be improved by more than 32% with approximate sorting for when the number of packets is less than 10K at any given time. If the number of packets in the arriving buffer is greater than 10K, we can divide them into smaller portions to achieve similar gains.

Given a simple directed graph $D = (V,A)$, let the size of the largest induced acyclic subgraph \em(dag) of $D$ be denoted by mas$(D)$. Let $D \in \mathcal{D}(n,p)$ be a random instance, obtained by choosing each of the ${{n}\choose{2}}$ 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) \geq \lfloor 2\log_{q} np - X \rfloor$, where $q = (1-p)^{-1}$, $X=1$ if $p \geq n^{-1/3+\epsilon}$ ($\epsilon > 0$ is any constant), $X=W/(\ln q)$ if $p \geq C/n$, where $W>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 $\log_{q} np + \Theta(\sqrt{\log_{q} np})$. Our results also carry over to a related model $\mathcal{D}_2(n,p)$ in which each possible directed arc is chosen independently with probability $p$.

We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.

We consider constrained proper edge colorings of the following type: Given a positive integer j and a family $\mathcal{F}$ of connected graphs on three or more vertices, we require that the subgraph formed by the union of any j color classes has no copy of any member of $\mathcal{F}$. This generalizes some well-known types of colorings such as acyclic edge colorings, distance-2 edge colorings, low treewidth edge colorings, etc. For such a generalization of restricted colorings, we obtain an upper bound of $O(d^{\max(\theta,1)})$ on the minimum number of colors used in such a coloring. Here d refers to the maximum degree of the graph, and $\theta$ is a parameter defined by $\theta=\theta(j,\mathcal{F})=\mathit{SUP}_{H\in\mathcal{F}}\frac{(|V(H)|-2)}{(|E(H)|-j)}$, where SUP stands for the supremum. Our proof is based on probabilistic arguments. In particular, we obtain $O(d)$ upper bounds for proper edge colorings with various interesting restrictions placed on the union of color classes. For example, we obtain $O(d)$ upper bounds on edge colorings with restrictions such as (i) the union of any three color classes should be an outerplanar graph, (ii) the union of any four color classes should have treewidth at most 2, (iii) the union of any five color classes should be planar, (iv) the union of any 16 color classes should be 5-degenerate, etc. We also consider generalizations where we require simultaneously for several pairs $(j_i,\mathcal{F}_i)$ ($i=1,\dots,s$) that the union of any $j_i$ color classes has no copy of any member of $\mathcal{F}_i$ and obtain upper bounds on the corresponding chromatic indices. As a corollary, we obtain that each of the four restrictions above can be satisfied simultaneously using $O(d)$ colors. Some ways of improving the bounds are sketched. Also, if we drop the requirement that the edge coloring be proper, then an $O(d^{\theta})$ upper bound on the chromatic index is established. Further, the stated upper bounds are also bounds for the list analogues of these edge colorings.

A feedback vertex set ( fvs ) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3 n 1 − ϵ vertices, then there is a cycle of length at most 6/ϵ (for ϵ ≥ 1/2, we can even improve this to just 6).Using this, we obtain a O ((12 log k /log log k + 6) k n ω algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k . Here n ω is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took O ((2 k + 1) k n 2 ) time.We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.

We present new algorithms for k-coloring and minimum (/spl chi/(G)-) coloring random and semi-random k-colorable graphs in polynomial expected time. The random graphs are drawn from the G(n,p,k) model and the semi-random graphs are drawn from the G/sub SB/(n,p,k) model. In both models, an adversary initially splits the n vertices into k color classes, each of size /spl Theta/(n). Then the edges between vertices in different color classes are chosen one by one, according to some probability distribution. The model G/sub SB/(n,p,k) was introduced by A. Blum (1991) and with respect to randomness, it lies between the random model G(n,p,k) where all edges are chosen with equal probability and the worst-case model.