On sparse graphs with dense long paths

DOI10.1016/0898-1221(75)90037-1zbMath0328.05123OpenAlexW2066775922MaRDI QIDQ1226502

Ronald L. Graham, Paul Erdős, Endre Szemerédi

Publication date: 1975

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(75)90037-1

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20)

Related Items

Cumulative Space in Black-White Pebbling and Resolution, Lower bounds on communication overlap of networks, Rounds versus time for the two person pebble game, Quadratic lower bounds for algebraic branching programs and formulas, Explicit construction of linear sized tolerant networks, Largest component and node fault tolerance for grids, Sustained space and cumulative complexity trade-offs for data-dependent memory-hard functions, Unnamed Item, The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs, One node fault tolerance for caterpillars and starlike trees, A family of graphs with expensive depth-reduction, Matrix rigidity, Space bounds for a game on graphs, Explicit construction of linear sized tolerant networks. (Reprint), Minimum \(k\)-critical bipartite graphs, Proofs of Catalytic Space, A quadratic lower bound for algebraic branching programs, Shallow grates, Rounds versus time for the two person pebble game

Cites Work

• Unnamed Item
• Unnamed Item