Source author record

Nicolas Gastineau

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computational Complexity

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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

Dichotomies properties on computational complexity of S-packing coloring problems

This work establishes the complexity class of several instances of the S-packing coloring problem: for a graph G, a positive integer k and a non decreasing list of integers S = (s\_1 , ..., s\_k ), G is S-colorable, if its vertices can be partitioned into sets S\_i , i = 1,... , k, where each S\_i being a s\_i -packing (a set of vertices at pairwise distance greater than s\_i). For a list of three integers, a dichotomy between NP-complete problems and polynomial time solvable problems is determined for subcubic graphs. Moreover, for an unfixed size of list, the complexity of the S-packing coloring problem is determined for several instances of the problem. These properties are used in order to prove a dichotomy between NP-complete problems and polynomial time solvable problems for lists of at most four integers.

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

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.

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.

Nicolas Gastineau

Research overview

Is this your work?

7 publications

Packing colorings of subcubic outerplanar graphs

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

S-Packing Colorings of Cubic Graphs

Dichotomies properties on computational complexity of S-packing coloring problems

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

Completely Independent Spanning Trees in Some Regular Graphs

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

See the researcher in context

Building this map preview

Nicolas Gastineau

Research overview

Is this your work?

7 publications

Packing colorings of subcubic outerplanar graphs

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

S-Packing Colorings of Cubic Graphs

Dichotomies properties on computational complexity of S-packing coloring problems

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

Completely Independent Spanning Trees in Some Regular Graphs

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

See the researcher in context

Building this map preview

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