Personne
Abhishek Methuku
Cette personne n’est plus à l’EPFL
Publications associées (16)
Adaptive majority problems for restricted query graphs and for weighted sets
Abhishek Methuku, Balázs Keszegh
Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...
ELSEVIER2021On clique coverings of complete multipartite graphs
A clique covering of a graph G is a set of cliques of G such that any edge of G is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number scc(G) of a graph G, is de ...
ELSEVIER2020On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus
Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8
2020Edge colorings of graphs without monochromatic stars
In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...
ELSEVIER2020A simple proof for a forbidden subposet problem
The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1)
ELECTRONIC JOURNAL OF COMBINATORICS2020Avoiding long Berge cycles: the missing casesk=r+1 andk=r+2
The maximum size of anr-uniform hypergraph without a Berge cycle of length at leastkhas been determined for allk >= r+ 3 by Furedi, Kostochka and Luo and fork
2020Asyrnptotics for the Turan number of Berge-K-2,K-t
Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. Let F be a family of graphs. The Turan number of the family Berge-F is the maximum possible number of edges in an r-uniform hyp ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2019Saturation of Berge hypergraphs
Given a graph F, a hypergraph is a Berge-F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge-F-saturated if H does not contain a subhypergraph that is a Berge-F, but for any edge e is an element of E((H ...
ELSEVIER SCIENCE BV2019Linearity of saturation for Berge hypergraphs
For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of ...
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019Generalized Turan problems for disjoint copies of graphs
Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...
ELSEVIER2019