Source author record

Olivier Togni

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

14works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On List Coloring with Separation of the Complete Graph and Set System Intersections

We consider the following list coloring with separation problem: Given a graph $G$ and integers $a,b$ , find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|= a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$ , there exists an assignment $φ$ of sets of integers to the vertices of $G$ such that $φ(u)\subset L(u)$ and $|φ(v)|=b$ for any vertex $u$ and $φ(u)\cap φ(v)=\emptyset$ for any edge $uv$ . Such a value of $c$ is called the separation number of $(G,a,b)$ . Using a special partition of a set of lists for which we obtain an improved version of Poincaré's crible, we determine the separation number of the complete graph $K_n$ for some values of $a,b$ and $n$ , and prove bounds for the remaining values.

preprint2020arXiv

Choosability with Separation of Cycles and Outerplanar Graphs

We consider the following list coloring with separation problem of graphs: Given a graph $G$ and integers $a,b$ , find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|\le a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$ , there exists an assignment $φ$ of sets of integers to the vertices of $G$ such that $φ(u)\subset L(u)$ and $|φ(v)|=b$ for any vertex $v$ and $φ(u)\cap φ(v)=\emptyset$ for any edge $uv$ . Such a value of $c$ is called the separation number of $(G,a,b)$ . We also study the variant called the free-separation number which is defined analogously but assuming that one arbitrary vertex is precolored. We determine the separation number and free-separation number of the cycle and derive from them the free-separation number of a cactus. We also present a lower bound for the separation and free-separation numbers of outerplanar graphs of girth $g\ge 5$ .

preprint2020arXiv

Packing colorings of subcubic outerplanar graphs

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$ -packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$ , the distance between $x$ and $y$ is greater than $s_i$ . The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$ -packing coloring of a graph $G$ is called the packing chromatic number of $G$ , denoted $χ_ρ(G)$ . The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by $7$ . Furthermore, we prove that every subcubic triangle-free outerplanar graph has a $(1,2,2,2)$ -packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a $(1,2,2,2)$ -packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a $(1,2,2,3)$ -packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an $S$ -packing coloring for $S=(1,3,\ldots,3)$ , where $3$ appears $Δ$ times ( $Δ$ being the maximum degree of vertices), and this property does not hold if one of the integers $3$ is replaced by $4$ in the sequence $S$ .

preprint2016arXiv

A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

Gy{á}rf{á}s et al. and Zaker have proven that the Grundy number of a graph $G$ satisfies $Γ(G)\ge t$ if and only if $G$ contains an induced subgraph called a $t$ -atom.The family of $t$ -atoms has bounded order and contains a finite number of graphs.In this article, we introduce equivalents of $t$ -atoms for b-coloring and partial Grundy coloring.This concept is used to prove that determining if $φ(G)\ge t$ and $\partialΓ(G)\ge t$ (under conditions for the b-coloring), for a graph $G$ , is in XP with parameter $t$ .We illustrate the utility of the concept of $t$ -atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least $7$ .

preprint2016arXiv

S-Packing Colorings of Cubic Graphs

Given a non-decreasing sequence $S=(s\_1,s\_2, \ldots, s\_k)$ of positive integers, an {\em $S$ -packing coloring} of a graph $G$ is a mapping $c$ from $V(G)$ to $\{s\_1,s\_2, \ldots, s\_k\}$ such that any two vertices with color $s\_i$ are at mutual distance greater than $s\_i$ , $1\le i\le k$ . This paper studies $S$ -packing colorings of (sub)cubic graphs. We prove that subcubic graphs are $(1,2,2,2,2,2,2)$ -packing colorable and $(1,1,2,2,3)$ -packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order $38$ which is not $(1,2,\ldots,12)$ -packing colorable.

preprint2015arXiv

Subdivision into i-packings and S-packing chromatic number of some lattices

An $i$ -packing in a graph $G$ is a set of vertices at pairwise distance greater than $i$ . For a nondecreasing sequence of integers $S=(s\_{1},s\_{2},\ldots)$ , the $S$ -packing chromatic number of a graph $G$ is the least integer $k$ such that there exists a coloring of $G$ into $k$ colors where each set of vertices colored $i$ , $i=1,\ldots, k$ , is an $s\_i$ -packing. This paper describes various subdivisions of an $i$ -packing into $j$ -packings ($j\textgreater{}i$) for the hexagonal, square and triangular lattices. These results allow us to bound the $S$ -packing chromatic number for these graphs, with more precise bounds and exact values for sequences $S=(s\_{i}, i\in\mathbb{N}^{*})$ , $s\_{i}=d+ \lfloor (i-1)/n \rfloor$ .

preprint2014arXiv

Completely Independent Spanning Trees in Some Regular Graphs

Let $k\ge 2$ be an integer and $T_1,\ldots, T_k$ be spanning trees of a graph $G$ . If for any pair of vertices $(u,v)$ of $V(G)$ , the paths from $u$ to $v$ in each $T_i$ , $1\le i\le k$ , do not contain common edges and common vertices, except the vertices $u$ and $v$ , then $T_1,\ldots, T_k$ are completely independent spanning trees in $G$ . For $2k$ -regular graphs which are $2k$ -connected, such as the Cartesian product of a complete graph of order $2k-1$ and a cycle and some Cartesian products of three cycles (for $k=3$ ), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always $k$ .

preprint2014arXiv

Free choosability of the cycle

A graph $G$ is free $(a,b)$ -choosable if for any vertex $v$ with $b$ colors assigned and for any list of colors of size $a$ associated with each vertex $u\ne v$ , the coloring can be completed by choosing for $u$ a subset of $b$ colors such that adjacent vertices are colored with disjoint color sets. In this note, a necessary and sufficient condition for a cycle to be free $(a,b)$ -choosable is given. As a corollary, some choosability results are derived for graphs in which cycles are connected by a tree structure.

preprint2014arXiv

On Packing Colorings of Distance Graphs

The {\em packing chromatic number} $χ_ρ(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$ . This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$ , i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$ . We present lower and upper bounds for $χ_ρ(G(\mathbb{Z},D))$ , showing that for finite $D$ , the packing chromatic number is finite. Our main result concerns distance graphs with $D=\{1,t\}$ for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for $t\geq 447$ : $χ_ρ(G(\mathbb{Z},\{1,t\}))\leq 40$ if $t$ is odd and $χ_ρ(G(\mathbb{Z},\{1,t\}))\leq 81$ if $t$ is even.

preprint2014arXiv

On the family of $r$ -regular graphs with Grundy number $r+1$

The Grundy number of a graph $G$ , denoted by $Γ(G)$ , is the largest $k$ such that there exists a partition of $V(G)$ , into $k$ independent sets $V_1,\ldots, V_k$ and every vertex of $V_i$ is adjacent to at least one vertex in $V_j$ , for every $j < i$ . The objects which are studied in this article are families of $r$ -regular graphs such that $Γ(G) = r + 1$ . Using the notion of independent module, a characterization of this family is given for $r=3$ . Moreover, we determine classes of graphs in this family, in particular the class of $r$ -regular graphs without induced $C_4$ , for $r \le 4$ . Furthermore, our propositions imply results on partial Grundy number.

preprint2013arXiv

The Packing Coloring of Distance Graphs $D(k,t)$

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $p$ such that vertices of $G$ can be partitioned into disjoint classes $X_{1}, ..., X_{p}$ where vertices in $X_{i}$ have pairwise distance greater than $i$ . For $k < t$ we study the packing chromatic number of infinite distance graphs $D(k, t)$ , i.e. graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in \{k, t\}$ . We generalize results by Ekstein et al. for graphs $D (1, t)$ . For sufficiently large $t$ we prove that $χ_ρ(D(k, t)) \leq 30$ for both $k$ , $t$ odd, and that $χ_ρ(D(k, t)) \leq 56$ for exactly one of $k$ , $t$ odd. We also give some upper and lower bounds for $χ_ρ(D(k, t))$ with small $k$ and $t$ . Keywords: distance graph; packing coloring; packing chromatic number

preprint2012arXiv

Vectorial solutions to list multicoloring problems on graphs

For a graph $G$ with a given list assignment $L$ on the vertices, we give an algebraical description of the set of all weights $w$ such that $G$ is $(L,w)$ -colorable, called permissible weights. Moreover, for a graph $G$ with a given list $L$ and a given permissible weight $w$ , we describe the set of all $(L,w)$ -colorings of $G$ . By the way, we solve the {\sl channel assignment problem}. Furthermore, we describe the set of solutions to the {\sl on call problem}: when $w$ is not a permissible weight, we find all the nearest permissible weights $w'$ . Finally, we give a solution to the non-recoloring problem keeping a given subcoloring.

preprint2011arXiv

Choosability of a weighted path and free-choosability of a cycle

A graph $G$ with a list of colors $L(v)$ and weight $w(v)$ for each vertex $v$ is $(L,w)$ -colorable if one can choose a subset of $w(v)$ colors from $L(v)$ for each vertex $v$ , such that adjacent vertices receive disjoint color sets. In this paper, we give necessary and sufficient conditions for a weighted path to be $(L,w)$ -colorable for some list assignments $L$ . Furthermore, we solve the problem of the free-choosability of a cycle.

preprint2011arXiv

Every triangle-free induced subgraph of the triangular lattice is $(5m,2m)$ -choosable

A graph $G$ is $(a,b)$ -choosable if for any color list of size $a$ associated with each vertex, one can choose a subset of $b$ colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer $m\ge 1$ , every finite triangle-free induced subgraph of the triangular lattice is $(5m,2m)$ -choosable.

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.

Olivier Togni

Research overview

Is this your work?

14 publications

On List Coloring with Separation of the Complete Graph and Set System Intersections

Choosability with Separation of Cycles and Outerplanar Graphs

Packing colorings of subcubic outerplanar graphs

A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

S-Packing Colorings of Cubic Graphs

Subdivision into i-packings and S-packing chromatic number of some lattices

Completely Independent Spanning Trees in Some Regular Graphs

Free choosability of the cycle

On Packing Colorings of Distance Graphs

On the family of $r$ -regular graphs with Grundy number $r+1$

The Packing Coloring of Distance Graphs $D(k,t)$

Vectorial solutions to list multicoloring problems on graphs

Choosability of a weighted path and free-choosability of a cycle

Every triangle-free induced subgraph of the triangular lattice is $(5m,2m)$ -choosable

See the researcher in context

Building this map preview

Olivier Togni

Research overview

Is this your work?

14 publications

On List Coloring with Separation of the Complete Graph and Set System Intersections

Choosability with Separation of Cycles and Outerplanar Graphs

Packing colorings of subcubic outerplanar graphs

A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

S-Packing Colorings of Cubic Graphs

Subdivision into i-packings and S-packing chromatic number of some lattices

Completely Independent Spanning Trees in Some Regular Graphs

Free choosability of the cycle

On Packing Colorings of Distance Graphs

On the family of rrr-regular graphs with Grundy number r+1r+1r+1

The Packing Coloring of Distance Graphs D(k,t)D(k,t)D(k,t)

Vectorial solutions to list multicoloring problems on graphs

Choosability of a weighted path and free-choosability of a cycle

Every triangle-free induced subgraph of the triangular lattice is (5m,2m)(5m,2m)(5m,2m)-choosable

See the researcher in context

Building this map preview

On the family of $r$ -regular graphs with Grundy number $r+1$

The Packing Coloring of Distance Graphs $D(k,t)$

Every triangle-free induced subgraph of the triangular lattice is $(5m,2m)$ -choosable