Image de couverture de livre

Upper bounds on the theta function of random graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Feige, Uriel, Grinberg, Vadim
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
par: Alecu, Bogdan, et autres
Publié: (2024)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
par: Lachish, Oded, et autres
Publié: (2026)

Testing $C_k$-freeness in bounded-arboricity graphs
par: Eden, Talya, et autres
Publié: (2024)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
par: Baste, Julien
Publié: (2023)

Exact recovery of planted cliques in semi-random graphs
par: Khanna, Yash
Publié: (2020)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
par: Bodlaender, Hans L., et autres
Publié: (2025)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
par: An, Shinwoo, et autres
Publié: (2024)

Faster diameter computation in graphs of bounded Euler genus
par: Kluk, Kacper, et autres
Publié: (2025)

Planted clique recovery in random geometric graphs
par: Avrachenkov, Konstantin, et autres
Publié: (2025)

Reconstruction of geometric random graphs with the Simple algorithm
par: Stegehuis, Clara, et autres
Publié: (2024)

Testing H-freeness on sparse graphs, the case of bounded expansion
par: Humeau, Samuel, et autres
Publié: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
par: Michel, Lukas, et autres
Publié: (2024)

Fixed-magnetization Ising on random graphs up to reconstruction
par: Gheissari, Reza, et autres
Publié: (2025)

Large cliques and large independent sets: can they coexist?
par: Feige, Uriel, et autres
Publié: (2025)

Making an oriented graph acyclic using inversions of bounded or prescribed size
par: Bang-Jensen, Jørgen, et autres
Publié: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
par: Chudnovsky, Maria, et autres
Publié: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
par: Bonamy, Marthe, et autres
Publié: (2022)

Packing $K_r$s in bounded degree graphs
par: McKay, Michael, et autres
Publié: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
par: Kluk, Kacper, et autres
Publié: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
par: Esmer, Barış Can, et autres
Publié: (2022)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
par: Huiberts, Sophie, et autres
Publié: (2022)

On $G^p$-unimodality of radius functions in graphs: structure and algorithms
par: Chalopin, Jérémie, et autres
Publié: (2025)

Two New Upper Bounds for the Maximum k-plex Problem
par: Zheng, Jiongzhi, et autres
Publié: (2023)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
par: Manea, Florin, et autres
Publié: (2024)

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
par: Caporrella, Matteo, et autres
Publié: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
par: Wesołowski, Adam, et autres
Publié: (2025)

Height-bounded Lempel-Ziv encodings
par: Bannai, Hideo, et autres
Publié: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
par: Bencs, Ferenc, et autres
Publié: (2025)

Optimal bounds on a tree inference algorithm
par: Gardiner, Jack, et autres
Publié: (2024)

Improved bounds for group testing in arbitrary hypergraphs
par: De Bonis, Annalisa
Publié: (2024)

A basic lower bound for property testing
par: Fischer, Eldar
Publié: (2024)

Differentially private graph coloring
par: Xie, Michael, et autres
Publié: (2026)

Clique-free t-matchings in degree-bounded graphs
par: Paluch, Katarzyna, et autres
Publié: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
par: Kacham, Praneeth, et autres
Publié: (2023)

Tight bounds for the sensitivity of CDAWGs with left-end edits
par: Fujimaru, Hiroto, et autres
Publié: (2023)

The trace reconstruction problem for spider graphs
par: Sun, Alec, et autres
Publié: (2022)

The Canadian Traveller Problem on outerplanar graphs
par: Beaudou, Laurent, et autres
Publié: (2024)

Private graph colouring with limited defectiveness
par: Christiansen, Aleksander B. G., et autres
Publié: (2024)

Practical algorithms for Hierarchical overlap graphs
par: Talera, Saumya, et autres
Publié: (2024)