We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of Fertin et al.: If $G$ is a graph of maximum degree $\Delta$, then $G$ admits a degenerate star coloring using $O(\Delta^{3/2})$ colors. We use this result to prove that every graph of genus $g$ admits a degenerate star coloring with $O(g^{3/5})$ colors. It is also shown that these results are sharp up to a logarithmic factor.
COBISS.SI-ID: 16199769
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 well known that the spectral radius of a tree whose maximum degree is $\Delta$ cannot exceed $2\sqrt{\Delta-1}$. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed $\sqrt{8 \Delta} + 10$, and more generally, for all $d$-degenerate graphs, where the corresponding upper bound is $\sqrt{4d\Delta}$. Following this, we say that a graph $G$ is spectrally $d$-degenerate if every subgraph $H$ of $G$ has spectral radius at most $\sqrt{d\Delta(H)}$. In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally $d$-degenerate graph $G$ contains a vertex whose degree is at most $4d\log_2(\Delta(G)/d)$ (if $\Delta(G) \ge 2d$). It is shown that the dependence on $\Delta$ in this upper bound cannot be eliminated, as long as the dependence on $d$ is subexponential. It is also proved that the problem of deciding if a graph is spectrally $d$-degenerate is co-NP-complete.
COBISS.SI-ID: 16410457
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_0 ) 1$ such that there is no $c_0$-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.
COBISS.SI-ID: 16340313