6 papers
Sparse graphs with local covering conditions on edges
Debsoumya Chakraborti, Amirali Madani, Anil Maheshwari +1
In 1988, Erdős suggested the question of minimizing the number of edges in a connected -vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman…
Isomorphism for Random -Uniform Hypergraphs
Debsoumya Chakraborti, Alan Frieze, Simi Haber +1
We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random -uniform hypergraph , for a wide range…
The threshold for the full perfect matching color profile in a random coloring of random graphs
Debsoumya Chakraborti, Mihir Hasabnis
Consider a graph with a coloring of its edge set from a set . Let be the set of all edges colored with . Recently, Frieze defi…
Extremal graphs with local covering conditions
Debsoumya Chakraborti, Po-Shen Loh
We systematically study a natural problem in extremal graph theory, to minimize the number of edges in a graph with a fixed number of vertices, subject to a certain local condition…
Minimizing the numbers of cliques and cycles of fixed size in an -saturated graph
Debsoumya Chakraborti, Po-Shen Loh
This paper considers two important questions in the well-studied theory of graphs that are -saturated. A graph is called -saturated if does not contain a subgraph iso…
The game chromatic number of a random hypergraph
Debsoumya Chakraborti, Alan Frieze, Mihir Hasabnis
We consider the following game, played on a -uniform hypergraph . There are colors available and two players take it in turns to color vertices. A partial coloring is pro…