Source author record

Michał Farnik

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.AG math.CO math.GT

Catalog footprint

Research overview

2works

5topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On stable polynomial mappings

For given natural numbers $d_1,d_2$ let $Ω_2(d_1,d_2)$ be the set off all polynomial mappings $F=(f,g):\mathbb{C}^2\to\mathbb{C}^2$ such that deg $f\le d_1$ , deg $g\le d_2$ . We say that the mapping $F$ is topologically stable in $Ω_2(d_1,d_2)$ if for every small deformation $F_t\in Ω_2(d_1,d_2)$ the mapping $F_t$ is topologically equivalent to the mapping $F$ . The aim of this paper is to characterize the topologically stable mappings in $Ω_2(d_1,d_2)$ . In particular we show how to effectively determine a member of $Ω_2(d_1,d_2)$ with generic topology.

preprint2013arXiv

Beyond the Shannon's Bound

Let $G=(V,E)$ be a multigraph of maximum degree $Δ$ . The edges of $G$ can be colored with at most $\frac{3}{2}Δ$ colors by Shannon's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $Δ$ colors. Shannon's Theorem gives a bound of $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor}|E|$ . However, for $Δ=3$ , Kamiński and Kowalik [SWAT'10] showed that there is a 3-edge-colorable subgraph of size at least $\frac{7}{9}|E|$ , unless $G$ has a connected component isomorphic to $K_3+e$ (a $K_3$ with an arbitrary edge doubled). Here we extend this line of research by showing that $G$ has a $Δ$ -edge colorable subgraph with at least $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor-1}|E|$ edges, unless $Δ$ is even and $G$ contains $\fracΔ{2}K_3$ or $Δ$ is odd and $G$ contains $\frac{Δ-1}{2}K_3+e$ . Moreover, the subgraph and its coloring can be found in polynomial time. Our results have applications in approximation algorithms for the Maximum $k$ -Edge-Colorable Subgraph problem, where given a graph $G$ (without any bound on its maximum degree or other restrictions) one has to find a $k$ -edge-colorable subgraph with maximum number of edges. In particular, for every even $k \ge 4$ we obtain a $\frac{2k+2}{3k+2}$ -approximation and for every odd $k\ge 5$ we get a $\frac{2k+1}{3k}$ -approximation. When $4\le k \le 13$ this improves over earlier algorithms due to Feige et al. [APPROX'02]

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.