Source author record

Jakub Przybyło

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

9works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A note on the conflict-free chromatic index

Let $G$ be a graph with maximum degree $Δ$ and without isolated vertices. An edge colouring $c$ of $G$ is conflict-free if the closed neighbourhood of every edge includes a uniquely coloured element. The least number of colours admitting such $c$ is the conflict-free chromatic index of $G$ , denoted by $χ'_{CF}(G)$ . In "Conflict-free chromatic number versus conflict-free chromatic index" [J. Graph Theory, 2022; 99: 349--358] it was recently proved by means of the probabilistic method that $χ'_{CF}(G)\leq C_1\log_2Δ+C_2$ , where $C_1>337$ and $C_2$ are constants, whereas there are families of graphs with $χ'_{CF}(G)\geq (1-o(1))\log_2Δ$ . In this note we provide an explicit simple proof of the fact that $χ'_{CF}(G)\leq 3\log_2Δ+1$ , which is a corollary of a stronger result: $χ'_{CF}(G)\leq 3\log_2χ(G)+1$ . For this aim we prove a few auxiliary observations, implying in particular that $χ'_{CF}(G)\leq 4$ for bipartite graphs.

preprint2022arXiv

On triangle-free list assignments

We show that Bernshteyn's proof of the breakthrough result of Molloy that triangle-free graphs are choosable from lists of size $(1+o(1))Δ/\logΔ$ can be adapted to yield a stronger result. In particular one may prove that such list sizes are sufficient to colour any graph of maximum degree $Δ$ provided that vertices sharing a common colour in their lists do not induce a triangle in $G$ , which encompasses all cases covered by Molloy's theorem. This was thus far known to be true for lists of size $(1000+o(1))Δ/\logΔ$ , as implies a more general result due to Amini and Reed. We also prove that lists of length $2(r-2)Δ\log_2\log_2Δ/\log_2Δ$ are sufficient if one replaces the triangle by any $K_r$ with $r\geq 4$ , pushing also slightly the multiplicative factor of $200r$ from Bernshteyn's result down to $2(r-2)$ . All bounds presented are also valid within the more general setting of correspondence colourings.

preprint2020arXiv

Conflict-free chromatic number vs conflict-free chromatic index

A vertex coloring of a given graph $G$ is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e. a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of $G$ , denoted $χ_{CF}(G)$ . What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree $Δ$ ? Trivially, $χ_{CF}(G)\leq χ(G)\leq Δ+1$ , but it is far from optimal - due to results of Glebov, Szabó and Tardos, and of Bhyravarapu, Kalyanasundaram and Mathew, the answer in known to be $Θ\left(\ln^2Δ\right)$ . We show that the answer to the same question in the class of line graphs is $Θ\left(\lnΔ\right)$ - that is, the extremal value of the conflict-free chromatic index among graphs with maximum degree $Δ$ is much smaller than the one for conflict-free chromatic number. The same result for $χ_{CF}(G)$ is also provided in the class of near regular graphs, i.e. graphs with minimum degree $δ\geq αΔ$ .

preprint2020arXiv

The 1-2-3 Conjecture holds for graphs with large enough minimum degree

A simple graph more often than not contains adjacent vertices with equal degrees. This in particular holds for all pairs of neighbours in regular graphs, while a lot such pairs can be expected e.g. in many random models. Is there a universal constant $K$ , say $K=3$ , such that one may always dispose of such pairs from any given connected graph with at least three vertices by blowing its selected edges into at most $K$ parallel edges? This question was first posed in 2004 by Karoński, Łuczak and Thomason, who equivalently asked if one may assign weights $1,2,3$ to the edges of every such graph so that adjacent vertices receive distinct weighted degrees - the sums of their incident weights. This basic problem is commonly referred to as the 1-2-3 Conjecture nowadays, and has been addressed in multiple papers. Thus far it is known that weights $1,2,3,4,5$ are sufficient [J. Combin. Theory Ser. B 100 (2010) 347-349]. We show that this conjecture holds if only the minimum degree $δ$ of a graph is large enough, i.e. when $δ= Ω(\logΔ)$ , where $Δ$ denotes the maximum degree of the graph. The principle idea behind our probabilistic proof relies on associating random variables with a special and carefully designed distribution to most of the vertices of a given graph, and then choosing weights for major part of the edges depending on the values of these variables in a deterministic or random manner.

preprint2016arXiv

Asymptotically optimal neighbor sum distinguishing total colorings of graphs

Given a proper total $k$ -coloring $c:V(G)\cup E(G)\to\{1,2,\ldots,k\}$ of a graph $G$ , we define the value of a vertex $v$ to be $c(v) + \sum_{uv \in E(G)} c(uv)$ . The smallest integer $k$ such that $G$ has a proper total $k$ -coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number of $G$ , $χ"_Σ(G)$ . Pilśniak and Woźniak (2013) conjectured that $χ"_Σ(G)\leq Δ(G)+3$ for any simple graph with maximum degree $Δ(G)$ . In this paper, we prove this bound to be asymptotically correct by showing that $χ"_Σ(G)\leq Δ(G)(1+o(1))$ . The main idea of our argument relies on Przybyło's proof (2014) regarding neighbor sum distinguishing edge-colorings.

preprint2015arXiv

Asymptotically optimal neighbour sum distinguishing total colourings of graphs

Consider a simple graph $G=(V,E)$ of maximum degree $Δ$ and its proper total colouring $c$ with the elements of the set $\{1,2,\ldots,k\}$ . The colouring $c$ is said to be \emph{neighbour sum distinguishing} if for every pair of adjacent vertices $u$ , $v$ , we have $c(u)+\sum_{e\ni u}c(e)\neq c(v)+\sum_{e\ni v}c(e)$ . The least integer $k$ for which it exists is denoted by $χ"_{\sum}(G)$ , hence $χ"_{\sum}(G) \geq Δ+1$ . On the other hand, it has been daringly conjectured that just one more label than presumed in the famous Total Colouring Conjecture suffices to construct such total colouring $c$ , i.e., that $χ"_{\sum}(G) \leq Δ+3$ for all graphs. We support this inequality by proving its asymptotic version, $χ"_{\sum}(G) \leq (1+o(1))Δ$ . The major part of the construction confirming this relays on a random assignment of colours, where the choice for every edge is biased by so called attractors, randomly assigned to the vertices, and the probabilistic result of Molloy and Reed on the Total Colouring Conjecture itself.

preprint2015arXiv

On an extremal problem in the class of 1-planar graphs

A graph $G=(V,E)$ is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite $1$ -planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most $3n-8$ edges, where $n$ denotes the order of a graph. We show that maximal-size bipartite $1$ -planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that maximal possible sizes of bipartite $1$ -planar graphs whose one partite set is much smaller than the other one tends towards $2n$ rather than $3n$ . In particular, we prove that if the size of the smaller partite set is sublinear in $n$ , then $|E|=(2+o(1))n$ , while the same is not true otherwise.

preprint2013arXiv

On the facial Thue choice number of plane graphs via entropy compression method

Let $G$ be a plane graph. A vertex-colouring $φ$ of $G$ is called {\em facial non-repetitive} if for no sequence $r_1 r_2 \dots r_{2n}$ , $n\geq 1$ , of consecutive vertex colours of any facial path it holds $r_i=r_{n+i}$ for all $i=1,2,\dots,n$ . A plane graph $G$ is {\em facial non-repetitively $l$ -choosable} if for every list assignment $L:V\rightarrow 2\sp{\mathbb{N}}$ with minimum list size at least $l$ there is a facial non-repetitive vertex-colouring $φ$ with colours from the associated lists. The {\em facial Thue choice number}, $π_{fl}(G)$ , of a plane graph $G$ is the minimum number $l$ such that $G$ is facial non-repetitively $l$ -choosable. %In this article we We use the so-called entropy compression method to show that $π_{fl} (G)\le c Δ$ for some absolute constant $c$ and $G$ a plane graph with maximum degree $Δ$ . Moreover, we give some better (constant) upper bounds on $π_{fl} (G)$ for special classes of plane graphs.

preprint2012arXiv

On the facial Thue choice index via entropy compression

A sequence is nonrepetitive if it contains no identical consecutive subsequences. An edge colouring of a path is nonrepetitive if the sequence of colours of its consecutive edges is nonrepetitive. By the celebrated construction of Thue, it is possible to generate nonrepetitive edge colourings for arbitrarily long paths using only three colours. A recent generalization of this concept implies that we may obtain such colourings even if we are forced to choose edge colours from any sequence of lists of size 4 (while sufficiency of lists of size 3 remains an open problem). As an extension of these basic ideas, Havet, Jendrol', Soták and Škrabul'áková proved that for each plane graph, 8 colours are sufficient to provide an edge colouring so that every facial path is nonrepetitively coloured. In this paper we prove that the same is possible from lists, provided that these have size at least 12. We thus improve the previous bound of 291 (proved by means of the Lovász Local Lemma). Our approach is based on the Moser-Tardos entropy-compression method and its recent extensions by Grytczuk, Kozik and Micek, and by Dujmović, Joret, Kozik and Wood.

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.