Almost exact matchings * (2009)
Abstract In the exact matching problem we are given a graph G, some of whose edges are coloredred, and a positive integer k. The goal is to determine if G has a perfect matching, exactly kedges of...
Abstract. In the Maximum Subset Matching problem, which generalizes the maximum matching problem, we are given a graph G = (V, E) and S ⊂ V. The goal is to determine the maximum number of vertices...
DISJOINT COLOR-AVOIDING TRIANGLES (2009)
Abstract. A set of pairwise edge-disjoint triangles of an edge-colored Kn is r-color avoiding if it does not contain r monochromatic triangles, each having a different color. Let fr(n) be the maximum...
A rainbow coloring of a graph is a coloring of the edges with distinct colors. We prove the following extension of Wilson’s Theorem. For every integer k there exists an n0 = n0(k) so that for all...
Almost given length cycles in digraphs (2009)
Abstract. A digraph is called k-cyclic if it cannot be made acyclic by removing less than k arcs. It is proved that for every ɛ> 0 there are constants K and δ so that for every d ∈ (0, δn),...
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP (2009)
Sets of permutations play an important role in the design of some efficient algorithms. In this paper we design two algorithms that manipulate sets of permutations. Both algorithms, each solving a...
The Effect of Induced Subgraphs on Quasi-Randomness (2009)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
Asymptotically optimal Kk-packings of dense graphs via fractional Kk-decompositions (2009)
Let H be a fixed graph. A fractional H-decomposition of a graph G is an assignment of nonnegative real weights to the copies of H in G such that for each e ∈ E(G), the sum of the weights of copies...
On the Density of a Graph and its Blowup (2009)
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n, p) contains the smallest density of copies of Kt,t, the complete...
On the Density of a Graph and its Blowup (2009)
Shapira, Asaf, Yuster, Raphael
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K_{t,t}, the...
The Effect of Induced Subgraphs on Quasi-Randomness (2009)
Shapira, Asaf, Yuster, Raphael
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P "behaves" like a truly random one. In the context...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Multigraphs (only) satisfy a weak triangle removal lemma (2009)
Shapira, Asaf, Yuster, Raphael
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph $G$ is {em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {em rainbow connectivity} of a connected graph $G$, denoted...
The Effect of Induced Subgraphs on Quasi-Randomness ∗ (2008)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
Zeev Nutov, Raphael Yuster, Israel Beniaminy, Clicksoftware Technologies
bins and I of items, where each j ∈ J has capacity c(j) and each i ∈ I has in bin j size ℓ(i, j) and profit p(i, j), find a maximum profit feasible assignment. The problem admits a...
Connected odd dominating sets in graphs (2008)
Yair Caro, William F. Klostermeyer, Raphael Yuster
An odd dominating set of a simple, undirected graph G = (V, E) is a set of vertices D ⊆ V such that |N[v] ∩ D | ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd...
Packing cliques in graphs with independence number 2 (2008)
Let G be a graph with no three independent vertices. How many edges of G can be packed with edge-disjoint copies of Kk? More specifically, let fk(n, m) be the largest integer t such that for any...
Single source shortest paths in $H$-minor free graphs (2008)
We present an algorithm for the Single Source Shortest Paths (SSSP) problem in \emph{$H$-minor free} graphs. For every fixed $H$, if $G$ is a graph with $n$ vertices having integer edge lengths and...
Hardness and Algorithms for Rainbow Connection (2008)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph $G$, denoted...
Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraete, Raphael Yuster
Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage,...
For every fixed graph $H$ and every fixed $0 < \alpha < 1$, we show that if a graph $G$ has the property that all subsets of size $\alpha n$ contain the ``correct'' number of copies of $H$ one would...
Connected odd dominating sets in graphs (2008)
Yair Caro, William F. Klostermeyer, Raphael Yuster
An odd dominating set of a simple, undirected graph G = (V, E) is a set of vertices D ⊆ V such that |N[v] ∩ D | ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd...
Mean Ramsey-Turán numbers (2008)
A ρ-mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph H and for ρ ≥ 1, the mean Ramsey-Turán number...
Fast algorithms for Maximum Subset Matching and All-Pairs Shortest Paths (2008)
in graphs with a (not so) small vertex cover
An H-factor of a graph G is a spanning subgraph of G whose connected components are isomorphic to H. Given a properly edge-colored graph G, arainbow H-subgraph of G is an H-subgraph of G whose edges...
A Turan type problem concerning the powers of the degrees of a graph, Electron (2008)
For a graph G whose degree sequence is d1,...,dn, and for a positive integer p, let ep(G) = �n i=1 dp i. For a fixed graph H, lettp(n, H) denote the maximum value of ep(G) taken over all graphs...
Let H be a graph on h vertices, and let G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is a(H)...
doi:10.1112/blms/bdl013 FRACTIONAL DECOMPOSITIONS OF DENSE HYPERGRAPHS (2008)
A seminal result of Rödl (the Rödl nibble) asserts that the edges of the complete r-uniform hypergraph Kr n can be packed, almost completely, with copies of Kr k,wherekisfixed. We prove that the...
The Effect of Induced Subgraphs on Quasi-Randomness (2008)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
Dominating a family of graphs with small connected subgraphs (2007)
Let F = fG 1; : : : ; G t g be a family of n-vertex graphs defined on the same vertex-set V, and let k be a positive integer. A subset of vertices D ae V is called an (F; k)-core if for each v 2 V...
and Tel Aviv University (2007)
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V; E). The...
The following asymptotic result is proved. For every ffl? 0, and for every positive integer h, there exists an n 0 = n 0 (ffl; h) such that for every graph H with h vertices and for every n? n 0, any...
Let H be a graph on h vertices, and let G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n=h vertex disjoint copies of H. The fractional arboricity of H is a(H)...
Yuster: Graphs with large variance (2007)
For a graph G, let V ar(G) denote the variance of the degree sequence of G, let sq(G) denote the sum of the squares of the degrees of G, and let t(G) denote the number of triangles in G and in its...
The Uniformity Space of Hypergraphs and its Applications (2007)
Let H = (V; E) be a hypergraph, and let F be a field. A function f: V! F is called stable if for each e 2 E, the sum of the values of f on the members of e is the same. The linear space consisting of...
Tree Decomposition of Graphs (2007)
Let H be a tree on h 2 vertices. It is shown that if G = (V; E) is a graph with ffi (G) jV j
Graphs Having the Local Decomposition Property (2007)
Let H be a fixed graph without isolated vertices, and let G be a graph on n vertices. Let 2 k n \Gamma 1 be an integer. We prove that if k n \Gamma 2 and every k-vertex induced subgraph of G is...
The Characterization of Zero-Sum (mod 2) Bipartite Ramsey Numbers (2007)
Let G be a bipartite graph, with k j e(G). The zero-sum bipartite Ramsey number B(G;Z k) is the smallest integer t such that in every Z k-coloring of the edges of K t;t, there is a zero-sum mod k...
A Note on Packing Trees into Complete Bipartite Graphs (2007)
Let fT 2;...; T t g be a sequence of trees, where T i has i vertices. We show that if t! 0:79n, then the sequence can be packed into the complete bipartite graph K n\Gamma1;n=2 (K n;(n\Gamma1)=2),...
A Note on Linear Coloring of Graphs (2007)
A proper vertex coloring of a graph is called linear if the subgraph induced by the vertices colored by any two colors is a set of vertex-disjoint paths. The linear chromatic number of a graph G,...
Zero-Sum Ascending Waves (2007)
Arie Bialostocki, Gui Bialostocki, Yair Caro, Raphael Yuster
A sequence of positive integers a 1 a 2... an is called an ascending monotone wave of
Optimal Factorizations of Families of Trees (2007)
Let fT 1; : : : ; T k g be a set of trees which is K h-packable. It is shown that every n-vertex graph G = (V; E) with ffi (G) n=2 + 3h
Noga Alon, Yair Caro, Raphael Yuster
Covering the edges of a graph by a prescribed tree with minimum overlap
An orthogonal coloring of a graph G is a pair fc 1; c 2 g of proper colorings of G, having the property that if two vertices are colored with the same color in c 1, then they must have distinct...
Dedicated to the memory of Paul Erdos For every fixed graph H, we determine the H-packing number of Kn, for all n? n 0 (H). We prove that if h is the number of edges of H, and gcd(H) = d is the...
H-Factors in Dense Graphs (2007)
The following asymptotic result is proved. For every ffl ? 0, and for every positive integer h, there exists an n 0 = n 0 (ffl; h) such that for every graph H with h vertices and for every n ? n 0 ,...
Graph Decomposition of Slim Graphs (2007)
A Graph G = (V; E) is called k-slim if for every subgraph S = (V S ; ES ) of G with s = jV S j k there exists K ae V S , jKj = k, such that the vertices of V S n K can be partitioned into two...
Efficient covering designs of the complete graph (2007)
Let H be a graph. We show that there exists n0 = n0(H) suchthatforevery n ≥ n0, there is a covering of the edges of Kn with copies of H where every edge is covered at most twice and any two copies...
E-mail: furedi math-inst.hu and (2007)
Endre Boros, Yair Caro, Zoltan Furedi, Raphael Yuster
A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let {(H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of {(H)...
A note on the number of edges guaranteeing a C 4 in Eulerian bipartite digraphs (2007)
Let G be an Eulerian bipartite digraph with vertex partition sizes m,n.We prove the following Turan-type result: If e(G) > 2mn/3thenG contains a directed cycle of length at most 4. The result is...
The order of monochromatic subgraphs with a given minimum degree (2007)
Let G be a graph. For a given positive integer d, letfG(d) denotethelargest integer t such that in every coloring of the edges of G with two colors there is a monochromatic subgraph with minimum...
Finding and counting given length cycles (Extended Abstract) (2007)
Noga Alon, Raphael Yuster, Uri Zwick
Abstract. We present an assortment of methods for nding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of...
Eulerian bipartite digraphs (2007)
Let G be an Eulerian bipartite digraph with vertex partition sizes m;n. We prove the following Turan-type result: If e(G)> 2mn=3 then G contains a directed cycle of length at most 4. The result is...
We present several new algorithms for detecting short fixed length cycles in digraphs. The new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming...
A comment on Ryser's conjecture for intersecting hypergraphs (2007)
Mansour, Toufik, Song, Chunwei, Yuster, Raphael
Let $\tau(\mathcal{H})$ be the cover number and $\nu(\mathcal{H})$ be the matching number of a hypergraph $\mathcal{H}$. Ryser conjectured that every $r$-partite hypergraph $\mathcal{H}$ satisfies...
Fractional decompositions of dense hypergraphs (2007)
A seminal result of Rödl (the Rödl nibble) asserts that the edges of the complete r-uniform hypergraph can be packed, almost completely, with copies of , where k is fixed. We prove that the same...
Approximation Algorithms and Hardness Results for Cycle Packing Problems (2007)
Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Yuster, Raphael Yuster
All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time (2007)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
In the all-pairs bottleneck paths (APBP) problem (a.k.a. allpairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time (2007)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for...
Maximum matching in graphs with an excluded minor (2007)
Abstract We present a new randomized algorithm for findinga maximum matching in H-minor free graphs. Forevery fixed H, our algorithm runs in O(n3!/(!+3)) < O(n1.326) time, where n is the number of...
Yair Caro, Arie Lev, Yehuda Roditty, Zsolt Tuza, Raphael Yuster
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the...
Finding heaviest H-subgraphs in real weighted graphs, with applications (2006)
Vassilevska, Virginia, Williams, Ryan, Yuster, Raphael
For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs MAX H-SUBGRAPH...
Decomposing oriented graphs into transitive tournaments, Discrete Mathematics 306 (2006)
For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then...
Finding the smallest H-subgraph in real weighted graphs and related problems (2006)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
Abstract. Let G be a graph with real weights assigned to the vertices (edges). The weight of a subgraph of G is the sum of the weights of its vertices (edges). The MIN H-SUBGRAPH problem is to find a...
Finding the smallest H-subgraph in real weighted graphs and related problems (2006)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
Abstract. Let G be a graph with real weights assigned to the vertices (edges). The weight of a subgraph of G is the sum of the weights of its vertices (edges). The MIN H-SUBGRAPH problem is to find a...
Finding the smallest H-subgraph in real weighted graphs and related problems (2006)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
Abstract. Let G be a graph with real weights assigned to the vertices (edges). The weight of a subgraph of G is the sum of the weights of its vertices (edges). The MIN H-SUBGRAPH problem is to find a...
Fractional decompositions of dense hypergraphs (2006)
A seminal result of Rödl (the Rödl nibble) asserts that the edges of the complete r-uniform hypergraph Knr can be packed, almost completely, with copies of Kkr, where k is fixed. We prove that the...
Fractional decompositions of dense hypergraphs (2006)
A seminal result of Rödl (the Rödl nibble) asserts that the edges of the complete r-uniform hypergraph Knr can be packed, almost completely, with copies of Kkr, where k is fixed. We prove that the...
Let H0 be a fixed hypergraph. A fractional H0-decomposition of a hypergraph H is an assignment of nonnegative real weights to the copies of H0 in H such that for each edge e ∈ E(H), the sum of the...
Mean Ramsey-Tur\'an numbers (2004)
A $\rho$-mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most $\rho$. For a graph $H$ and for $\rho \geq 1$, the {\em mean...
Packing directed cycles efficiently (2004)
Let G be a simple digraph. The dicycle packing number of G, denoted νc(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arcweight function...
Packing directed cycles efficiently (2004)
It is well known that **c (G, w) can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing yielding **c...
Asymptotically optimal $K_k$-packings of dense graphs via fractional $K_k$-decompositions (2003)
Let $H$ be a fixed graph. A {\em fractional $H$-decomposition} of a graph $G$ is an assignment of nonnegative real weights to the copies of $H$ in $G$ such that for each $e \in E(G)$, the sum of the...
We prove that every Eulerian orientation of $K_{m,n}$ contains $\frac{1}{4+\sqrt{8}}mn(1-o(1))$ arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument,...
Integer and fractional packing of families of graphs (2003)
Let ${\cal F}$ be a family of graphs. For a graph $G$, the {\em ${\cal F}$-packing number}, denoted $\nu_{{\cal F}}(G)$, is the maximum number of pairwise edge-disjoint elements of ${\cal F}$ in $G$....
The number of edge disjoint transitive triples in a tournament (2003)
We prove that a tournament with $n$ vertices has more than $0.13n^2(1+o(1))$ edge-disjoint transitive triples. We also prove some results on the existence of large packings of $k$-vertex transitive...
The Order of Monochromatic Subgraphs with a Given Minimum Degree (2003)
Let G be a graph. For a given positive integer d, let f G (d) denote the largest integer t such that in every coloring of the edges of G with two colors there is a monochromatic subgraph with minimum...
Second neighborhood via first neighborhood in digraphs (2003)
Guantao Chen, Jian Shen, Raphael Yuster
Let D be a simple digraph without loops or digons. For any v ∈ V (D), the first out-neighborhood N + (v) is the set of all vertices with out-distance 1 from v and the second neighborhood N ++ (v)...
The order of monochromatic subgraphs with a given minimum degree (2002)
Let $G$ be a graph. For a given positive integer $d$, let $f_G(d)$ denote the largest integer $t$ such that in every coloring of the edges of $G$ with two colors there is a monochromatic subgraph...
Tiling transitive tournaments and their blow-ups (2002)
Let $TT_k$ denote the transitive tournament on $k$ vertices. Let $TT(h,k)$ denote the graph obtained from $TT_k$ by replacing each vertex with an independent set of size $h \geq 1$. The following...
Families of trees decompose the random graph in any arbitrary way (2002)
Let $F=\{H_1,...,H_k\}$ be a family of graphs. A graph $G$ with $m$ edges is called {\em totally $F$-decomposable} if for {\em every} linear combination of the form $\alpha_1 e(H_1) + ... + \alpha_k...
Equitable coloring of k-uniform hypergraphs (2002)
Let $H$ be a $k$-uniform hypergraph with $n$ vertices. A {\em strong $r$-coloring} is a partition of the vertices into $r$ parts, such that each edge of $H$ intersects each part. A strong...
Edge coloring complete uniform hypergraphs with many components (2002)
Let $H$ be a hypergraph. For a $k$-edge coloring $c : E(H) \to \{1,...,k\}$ let $f(H,c)$ be the number of components in the subhypergraph induced by the color class with the least number of...
The domatic number of regular and almost regular graphs (2001)
The domatic number of a graph $G$, denoted $dom(G)$, is the maximum possible cardinality of a family of disjoint sets of vertices of $G$, each set being a dominating set of $G$. It is well known that...
Connected Domination and Spanning Trees with Many Leaves (2000)
Yair Caro, Douglas B. West, Raphael Yuster
Abstract Let G = (V; E) be a connected graph. A connected dominating set S ae V is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted fl
Orthogonal decomposition and packing of complete graphs (1999)
An H-decomposition of a graph G is a partition of the edge-set of G into subsets, where each subset induces a copy of the graph H. A k-orthogonal H-decomposition of a graph G is a set of k...
Decomposing large graphs with small graphs of high density (1999)
It is shown that for every positive integer h, and for every ffl? 0, there are graphs H = (V H; EH) with at least h vertices and with density at least 0:5 \Gamma ffl with the following property: If G...
Packing and covering of dense graphs (1998)
Noga Alon, Yair Caro, Raphael Yuster
Let d be a positive integer. A graph G is called d-divisible if d divides the degree of each vertex of G. G is called nowhere d-divisible if no degree of a vertex of G is divisible by d. For a graph...
Packing and covering of dense graphs (1998)
Noga Alon, Yair Caro, Raphael Yuster
Let d be a positive integer. A graph G is called d-divisible if d divides the degree of each vertex of G. G is called nowhere d-divisible if no degree of a vertex of G is divisible by d. For a graph...
Covering graphs: The covering problem solved (1998)
For every fixed graph H, we determine the H-covering number of Kn, for all n? n 0 (H). We prove that if h is the number of edges of H, and gcd(H) = d is the greatest common divisor of the degrees of...
Orthogonal Colorings of Graphs (1998)
An orthogonal coloring of a graph G is a pair fc 1 ; c 2 g of proper colorings of G, having the property that if two vertices are colored with the same color in c 1 , then they must have distinct...
Orthogonal Colorings of Graphs (1998)
An orthogonal coloring of a graph G is a pair {c 1 ,c 2 } of proper colorings of G,having thepropertythatiftwoverticesarecoloredwiththesamecolorinc 1 , then they must have distinct colors in c 2 ....
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
Packing graphs: The packing problem solved (1997)
Dedicated to the memory of Paul Erdős For every fixed graph H, we determine the H-packing number of Kn, for all n>n0(H). We prove that if h is the number of edges of H, and gcd(H) =dis the...
Independent transversals in r-partite graphs (1997)
Let G(r; n) denote the set of all r-partite graphs consisting of n vertices in each partite class. An independent transversal of G 2 G(r; n) is an independent set consisting of exactly one vertex...
y We prove the intersection conjecture for designs: For any complete graph K r there is a finite set of positive integers M (r) such that for every n? n 0 (r), if Kn has a K r-decomposition (namely a...
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
Packing Graphs: The packing problem solved (1997)
Yair Caro And, Yair Caro, Raphael Yuster
For every fixed graph H, we determine the H-packing number of Kn , for all n ? n 0 (H). We prove that if h is the number of edges of H, and gcd(H) = d is the greatest common divisor of the degrees of...
Efficient Covering Designs of the Complete Graph (1997)
Let H be a graph. We show that there exists n 0 = n 0 (H) such that for every n n 0 , there is a covering of the edges of Kn with copies of H where every edge is covered at most twice and any two...
Independent Transversals and Independent Coverings in Sparse Partite Graphs (1997)
Raphael Yuster, Beverly Sackler
An [n; k; r]-partite graph is a graph whose vertex set, V , can be partitioned into n pairwisedisjoint independent sets, V 1 ; . . . ; Vn , each containing exactly k vertices, and the subgraph...
Efficient Covering Designs of the Complete Graph (1997)
Let H be a graph. We show that there exists n 0 = n 0 (H) such that for every n n 0 , there is a covering of the edges of Kn with copies of H where every edge is covered at most twice and any two...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every fixed graph H with h vertices, any graph G with n vertices and with minimum degree d ≥ χ(H)−1 χ(H) n contains (1 − o(1))n/h vertex...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every ɛ> 0, and for every positive integer h, there exists an n0 = n0(ɛ, h) such that for every graph H with h vertices and for every n> n0, any...
The number of edge colorings with no monochromatic triangle (1996)
Let F (n; k) denote the maximum number of two edge colorings of a graph on n vertices that admit no monochromatic K k, (a complete graph on k vertices). The following results are proved: F (n; 3) = 2...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every fixed graph H with h vertices, any graph G with n vertices and with minimum degree d (H)\Gamma1
Finding Even Cycles Even Faster (1996)
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k 2, there is an O(V 2 ) time algorithm that decides whether an...
Packing Graphs: The packing problem solved (1996)
For every fixed graph H, we determine the H-packing number of Kn , for all n ? n 0 (H). We prove that if h is the number of edges of H, and gcd(H) = d is the greatest common divisor of the degrees of...
The 123 Theorem and its extensions (1995)
It is shown that for every b> a> 0 and for every two independent identically distributed real random variables X and Y P rob[|X − Y | ≤ b] < (2⌈b/a ⌉ − 1)P rob[|X − Y | ≤ a]....
Finding and Counting Given Length Cycles (1995)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
The 123 Theorem and its extensions (1995)
Noga Alon And, Noga Alon, Raphael Yuster
It is shown that for every b ? a ? 0 and for every two independent identically distributed real random variables X and Y P rob[jX \Gamma Y j b] ! (2db=ae \Gamma 1)P rob[jX \Gamma Y j a]: This is...
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V, E). The...
Finding even cycles even faster (1994)
Abstract. We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V 2) time algorithm that decides...
Finding even cycles even faster (1994)
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k 2, there is an O(V 2) time algorithm that decides whether an...
Covering Non-Uniform Hypergraphs
Endre Boros, Yair Caro, Zoltan Furedi, Raphael Yuster
A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let #(H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of #(H)...
Connected Domination and Spanning Trees with Many Leaves
Yair Caro, Douglas B. West, Raphael Yuster
Let G = (V; E) be a connected graph. A connected dominating set S V is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted c (G), is the minimum...