Source author record

Zbigniew Lonc

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws

For graphs $G$ and $H$ , an $H$ -coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$ . In the $H$ -Coloring problem the graph $H$ is fixed and we ask whether an instance graph $G$ admits an $H$ -coloring. A generalization of this problem is $H$ -ColoringExt, where some vertices of $G$ are already mapped to vertices of $H$ and we ask if this partial mapping can be extended to an $H$ -coloring. We study the complexity of variants of $H$ -Coloring in $F$ -free graphs, i.e., graphs excluding a fixed graph $F$ as an induced subgraph. For integers $a,b,c \geq 1$ , by $S_{a,b,c}$ we denote the graph obtained by identifying one endvertex of three paths on $a+1$ , $b+1$ , and $c+1$ vertices, respectively. For odd $k \geq 5$ , by $W_k$ we denote the graph obtained from the $k$ -cycle by adding a universal vertex. As our main algorithmic result we show that $W_5$ -ColoringExt is polynomial-time solvable in $S_{2,1,1}$ -free graphs. This result exhibits an interesting non-monotonicity of $H$ -ColoringExt with respect to taking induced subgraphs of $H$ . Indeed, $W_5$ contains a triangle, and $K_3$ -Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., $S_{1,1,1}$ -free) graphs. Our algorithm is based on two main observations: 1. $W_5$ -ColoringExt in $S_{2,1,1}$ -free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2. the latter problem can be solved in polynomial time in $S_{2,1,1}$ -free graphs. We complement this algorithmic result with several negative ones. In particular, we show that $W_5$ -ColoringExt is NP-hard in $S_{3,3,3}$ -free graphs. This is again uncommon, as usually problems that are NP-hard in $S_{a,b,c}$ -free graphs for some constant $a,b,c$ are already hard in claw-free graphs.

preprint2020arXiv

Dilworth's Theorem for Borel Posets

A famous theorem of Dilworth asserts that any finite poset of width $k$ can be decomposed into $k$ chains. We study the following problem: given a Borel poset $P$ of finite width $k$ , is it true that it can be decomposed into $k$ Borel chains? We give a positive answer in a special case of Borel posets embeddable into the real line. We also prove a dual theorem for posets whose comparability graphs are locally countable.

preprint2011arXiv

Constructions of asymptotically shortest k-radius sequences

Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f_k(n) denote the length of a shortest k-radius sequence over A. We provide constructions demonstrating that (1) for every fixed k and for every fixed e>0, f_k(n) = n^2/(2k) +O(n^(1+e)) and (2) for every k, where k is the integer part of n^a for some fixed real a such that 0 < a <1, f_k(n) = n^2/(2k) +O(n^b), for some b <2-a. Since f_k(n) >= n^2/(2k) - n/(2k), the constructions give asymptotically optimal k-radius sequences. Finally, (3) we construct optimal 2-radius sequences for a 2p-element alphabet, where p is a prime.

preprint2010arXiv

On graph equivalences preserved under extensions

Let R be an equivalence relation on graphs. By the strengthening of R we mean the relation R' such that graphs G and H are in the relation R' if for every graph F, the union of the graphs G and F is in the relation R with the union of the graphs H and F. We study strengthenings of equivalence relations on graphs. The most important case that we consider concerns equivalence relations defined by graph properties. We obtain results on the strengthening of equivalence relations determined by the properties such as being a k-connected graph, k-colorable, hamiltonian and planar.

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.