Source author record

Konstanty Junosza-Szaniawski

Konstanty Junosza-Szaniawski appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

What is connected

7works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Coloring distance graphs on the plane

We consider the coloring of certain distance graphs on the Euclidean plane. Namely, we ask for the minimal number of colors needed to color all points of the plane in such a way that pairs of points at distance in the interval $[1,b]$ get different colors. The classic Hadwiger-Nelson problem is a special case of this question -- obtained by taking $b=1$. The main results of the paper are improved lower and upper bounds on the number of colors for some values of $b$. In particular, we determine the minimal number of colors for two ranges of values of $b$ - one of which is enlarging an interval presented by Exoo and the second is completely new. Up to our knowledge, these are the only known families of distance graphs on the plane with a determined nontrivial chromatic number. Moreover, we present the first $8$-coloring for $b$ larger than values of $b$ for the known $7$-colorings. As a byproduct, we give some bounds and exact values for bounded parts of the plane, specifically by coloring certain annuli.

preprint2022arXiv

Online coloring of disk graphs

In this paper, we give a family of online algorithms for the classical coloring problem of intersection graphs of discs with bounded diameter. Our algorithms make use of a geometric representation of such graphs and are inspired by an algorithm of Fiala et al., but have better competitive ratios. The improvement comes from using two techniques of partitioning the set of vertices before coloring them. One of whichis an application of a b-fold coloring of the plane. The method is more general and we show how it can be applied to coloring other shapes on the plane as well as adjust it for online L(2, 1)-labeling.

preprint2016arXiv

Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique

We study the {\sc Clique} problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straight-line-segment intersection graphs, but solvable in polynomial time in intersection graphs of homothetic triangles. We extend the latter result by showing that for every convex polygon $P$ with sides parallel to $k$ directions, every $n$-vertex graph which is an intersection graph of homothetic copies of $P$ contains at most $n^{k}$ inclusion-wise maximal cliques. We actually prove this result for a more general class of graphs, the so called $k_{\text{DIR}}-\text{CONV}$, which are intersection graphs of convex polygons whose sides are parallel to some fixed $k$ directions. Moreover, we provide some lower bounds on the numbers of maximal cliques, discuss the complexity of recognizing these classes of graphs and present a relationship with other classes of convex-set intersection graphs. Finally, we generalize the upper bound on the number of maximal cliques to intersection graphs of higher-dimensional convex polytopes in Euclidean space.

preprint2015arXiv

Counting independent sets via Divide Measure and Conquer method

In this paper we give an algorithm for counting the number of all independent sets in a given graph which works in time $O^*(1.1394^n)$ for subcubic graphs and in time $O^*(1.2369^n)$ for general graphs, where $n$ is the number of vertices in the instance graph, and polynomial space. The result comes from combining two well known methods "Divide and Conquer" and "Measure and Conquer". We introduce this new concept of Divide, Measure and Conquer method and expect it will find applications in other problems. The algorithm of Björklund, Husfeldt and Koivisto for graph colouring with our algorithm used as a subroutine has complexity $O^*(2.2369^n)$ and is currently the fastest graph colouring algorithm in polynomial space.

preprint2015arXiv

First non-trivial upper bound on the circular chromatic number of the plane

We consider circular version of the famous Nelson-Hadwiger problem. It is know that 4 colors are necessary and 7 colors suffice to color the euclidean plane in such a way that points at distance one get different colors. In $r$-circular coloring we assign arcs of length one of a circle with a perimeter $r$ in such a way that points at distance one get disjoint arcs. In this paper we show the existence of $r$-circular coloring for $r=4+\frac{4\sqrt{3}}{3}\approx 6.30$. It is the first result with $r$-circular coloring of the plane with $r$ smaller than 7. We also show $r$-circular coloring of the plane with $r<7$ in the case when we require disjoint arcs for points at distance belonging to the internal $[\frac{10}{11}, \frac{12}{11}]$.

preprint2013arXiv

An Exact Algorithm for the Generalized List $T$-Coloring Problem

The generalized list $T$-coloring is a common generalization of many graph coloring models, including classical coloring, $L(p,q)$-labeling, channel assignment and $T$-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for such a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time $\mathcal{O}^*((τ+2)^n)$, where $τ$ is the maximum forbidden difference over all edges of the input graph and $n$ is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.

preprint2011arXiv

Determining L(2,1)-Span in Polynomial Space

A $k$-L(2,1)-labeling of a graph is a function from its vertex set into the set $\{0,...,k\}$, such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. It is known that finding the smallest $k$ admitting the existence of a $k$-L(2,1)-labeling of any given graph is NP-Complete. In this paper we present an algorithm for this problem, which works in time $O(\complexity ^n)$ and polynomial memory, where $\eps$ is an arbitrarily small positive constant. This is the first exact algorithm for L(2,1)-labeling problem with time complexity $O(c^n)$ for some constant $c$ and polynomial space complexity.