Source author record

Jens Schreyer

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

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.