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
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
Let $G$ be an unweighted graph of complexity $n$ embedded in a surface of genus $g$, orientable or not. We describe improved algorithms to compute a shortest non-contractible and a shortest non-separating cycle in $G$. If $k$ is an integer, we can compute such a non-trivial cycle with length at most $k$ in $O(gnk)$ time, or correctly report that no such cycle exists. In particular, on a fixed surface, we can test in linear time whether the edge-width or face-width of a graph is bounded from above by a constant. This also implies an output-sensitive algorithm to compute a shortest non-trivial cycle that runs in $O(gnk_0)$ time, where $k_0$ is the length of the cycle. We also give an approximation algorithm for the shortest non-trivial cycle. If a parameter $0( \varepsilon ( 1$ is given, we compute in $O(gn/\varepsilon)$ time a non-trivial cycle whose length is at most $1+\varepsilon$ times the length of the shortest non-trivial cycle.
COBISS.SI-ID: 16093017