Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs

DOI10.1137/140980181zbMath1345.05094OpenAlexW2523358926MaRDI QIDQ2821620

C. R. Subramanian, Kunal Dutta

Publication date: 22 September 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140980181

zbMATH Keywords

random graphsdirected graphsmeasure concentrationmaximum induced acyclic subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Coloring random graphs
• On the independence number of random graphs
• Expose-and-merge exploration and the chromatic number of a random graph
• Finding induced acyclic subgraphs in random digraphs
• The transitive closure of a random digraph
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• The approximation of maximum subgraph problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs