Source author record

Erika Škrabuľáková

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

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2015arXiv

The Thue choice number versus the Thue chromatic number of graphs

We say that a vertex colouring $φ$ of a graph $G$ is nonrepetitive if there is no positive integer $n$ and a path on $2n$ vertices $v_{1}\ldots v_{2n}$ in $G$ such that the associated sequence of colours $φ(v_{1})\ldotsφ(v_{2n})$ satisfy $φ(v_{i})=φ(v_{i+n})$ for all $i=1,2,\dots,n$ . The minimum number of colours in a nonrepetitive vertex colouring of $G$ is the Thue chromatic number $π(G)$ . For the case of vertex list colourings the Thue choice number $π_{l}(G)$ of $G$ denotes the smallest integer $k$ such that for every list assignment $L:V(G)\rightarrow 2^{\mathbb{N}}$ with minimum list length at least $k$ , there is a nonrepetitive vertex colouring of $G$ from the assigned lists. Recently it was proved that the Thue chromatic number and the Thue choice number of the same graph may have an arbitrary large difference in some classes of graphs. Here we give an overview of the known results where we compare these two parameters for several families of graphs and we also give a list of open problems on this topic.

preprint2014arXiv

A note on the Thue chromatic number of lexicographic products of graphs

A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$ ). Let $G$ be a graph whose vertices are coloured. A colouring $φ$ of the graph $G$ is non-repetitive if the sequence of colours on every path in $G$ is non-repetitive. The Thue chromatic number, denoted by $π(G)$ , is the minimum number of colours of a non-repetitive colouring of $G$ . In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product $G\circ H$ of graphs $G$ and $H$ with respect to some properties of the factors. This upper bound is then used to derive the exact values for $π(G\circ H)$ when $G$ is a complete multipartite graph and $H$ is an arbitrary graph.

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.

preprint2013arXiv

Total Thue colourings of graphs

A total colouring of a graph is a colouring of its vertices and edges such that no two adjacent vertices or edges have the same colour and moreover, no edge coloured $c$ has its endvertex coloured $c$ too. A weak total Thue colouring of a graph $G$ is a colouring of its vertices and edges such that the colour sequence of consecutive vertices and edges of every path of $G$ is nonrepetitive. In a total Thue colouring also the induced vertex-colouring and edge-colouring of $G$ are nonrepetitive. The weak total Thue number $π_{T_w}(G)$ of a graph $G$ denotes the minimum number of colours required in every weak total Thue colouring and the minimum number of colours required in every total Thue colouring is called the total Thue number $π_T$ . Here we show some upper bounds for both parameters depending on the maximum degree or size of the graph. We also give some lower bounds and some better upper bounds for these graph parameters considering special families of graphs.

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.