Chapter in the Handbook of Graph Theory (CRC Press) describing Graph Limits. The content includes: Graphons, Homomorphism Density, Convergent Sequences of Graphs and Graphons, Metric Space Topology on Graphs and Graphons, Regularity Lemma and Approximation of Graphons by Weighted Graphs, W-Random Graphs, Graph Parameters and Connection Matrices, Extremal Graph Theory and the Algebra of Quantum Graphs.
COBISS.SI-ID: 16921945
It is shown that, in every family $\mathscr{G}$ of graphs that is closed under taking minors, the following properties are roughly equivalent for every $G \in \mathscr{G}$: (a) $G$ has many large eigenvalues; (b) $G$ has many large negative eigenvalues; (c) $G$ has many vertices of large degree. By a rough equivalence we mean that, in the quantitative version of the result, specifying the values of "how many" eigenvalues we want and "how large" they are, each implication may change these values by a constant factor.
COBISS.SI-ID: 16648537
We show that, if P$\ne$NP, there is a constant c ) 1 such that there is no polynomial-time c-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.
COBISS.SI-ID: 16340313