38 citations · 61 across the 21 of their papers we have counts for
28 papers
On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
In this paper, we study the existence problem of completely independent spanning trees (CIST) in chordal graphs through appropriate hypergraph representations and their panchromati…
Constructing two completely independent spanning trees in dual-cubes
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
In this paper, we prove the existence of two completely independent spanning trees in the -dimensional dual-cube , a variant of the hypercube, for every . To this…
Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
We study completely independent spanning trees (CIST), \textit{i.e.}, trees that are both edge-disjoint and internally vertex-disjoint, in split graphs. We establish a corresponden…
Hypergraphs with Polynomial Representation: Introducing -splits
François Pitois, Mohammed Haddad, Hamida Seba +1
Inspired by the split decomposition of graphs and rank-width, we introduce the notion of -splits. We focus on the family of -splits of a graph of order , and we prove that…
On List Coloring with Separation of the Complete Graph and Set System Intersections
Jean-Christophe Godin, Rémi Grisot, Olivier Togni
We consider the following list coloring with separation problem: Given a graph and integers , find the largest integer such that for any list assignment of wit…
Leader Election And Local Identifiers For 3D Programmable Matter
Nicolas Gastineau, Wahabou Abdou, Nader Mbarek +1
In this paper, we present two deterministic leader election algorithms for programmable matter on the face-centered cubic grid. The face-centered cubic grid is a 3-dimensional 12-r…
Choosability with Separation of Cycles and Outerplanar Graphs
Jean-Christophe Godin, Olivier Togni
We consider the following list coloring with separation problem of graphs: Given a graph and integers , find the largest integer such that for any list assignment …
New reducible configurations for graph multicoloring with application to the experimental resolution of McDiarmid-Reed's Conjecture (extended version)
Jean-Christophe Godin, Olivier Togni
A -coloring of a graph associates to each vertex a -subset of a set of colors in such a way that the color-sets of adjacent vertices are disjoint. We define gener…
Exact distance graphs of product graphs
Boštjan Brešar, Nicolas Gastineau, Sandi Klavžar +1
Given a graph , the exact distance- graph has as its vertex set, and two vertices are adjacent whenever the distance between them in equals .…
Packing colorings of subcubic outerplanar graphs
Boštjan Brešar, Nicolas Gastineau, Olivier Togni
Given a graph and a nondecreasing sequence of positive integers, the mapping is called an -packing coloring of $G…
Distributed leader election and computation of local identifiers for programmable matter
Nicolas Gastineau, Wahabou Abdou, Nader Mbarek +1
The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the…
Coloring of the dth power of the face-centered cubic grid
Nicolas Gastineau, Olivier Togni
The face-centered cubic grid is a three dimensional 12-regular infinite grid. This graph represents an optimal way to pack spheres in the three-dimensional space. In this grid, the…
On S-packing edge-colorings of cubic graphs
Nicolas Gastineau, Olivier Togni
Given a non-decreasing sequence S = (s 1,s 2,. .. ,s k) of positive integers, an S-packing edge-coloring of a graph G is a partition of the edge set of G into k subsets {X 1 ,X 2,.…
On packing chromatic number of subcubic outerplanar graphs
Nicolas Gastineau, P{ř}emysl Holub, Olivier Togni
Although it has recently been proved that the packing chromatic number is unbounded on the class of subcubic graphs, there exists subclasses in which the packing chromatic number i…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
Benoit Darties, Nicolas Gastineau, Olivier Togni
The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently compl…
Subdivision into i-packings and S-packing chromatic number of some lattices
Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni
An -packing in a graph is a set of vertices at pairwise distance greater than . For a nondecreasing sequence of integers , the -packing chrom…
A characterization of b-chromatic and partial Grundy numbers by induced subgraphs
Brice Effantin, Nicolas Gastineau, Olivier Togni
Gy{á}rf{á}s et al. and Zaker have proven that the Grundy number of a graph satisfies if and only if contains an induced subgraph called a -atom.The family of…
Completely Independent Spanning Trees in Some Regular Graphs
Benoit Darties, Nicolas Gastineau, Olivier Togni
Let be an integer and be spanning trees of a graph . If for any pair of vertices of , the paths from to in each , $1\le i\l…
Free choosability of the cycle
Yves Aubry, Jean-Christophe Godin, Olivier Togni
A graph is free -choosable if for any vertex with colors assigned and for any list of colors of size associated with each vertex , the coloring can b…
S-Packing Colorings of Cubic Graphs
Nicolas Gastineau, Olivier Togni
Given a non-decreasing sequence of positive integers, an {\em -packing coloring} of a graph is a mapping from to $\{s\_1,s\_2, \ldot…
On the family of -regular graphs with Grundy number
Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni
The Grundy number of a graph , denoted by , is the largest such that there exists a partition of , into independent sets and every vertex o…
The Packing Coloring of Distance Graphs
Jan Ekstein, Přemysl Holub, Olivier Togni
The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertic…
Radio Labelings of Distance Graphs
R. Čada, J. Ekstein, P. Holub +1
A radio -labeling of a connected graph is an assignment of non negative integers to the vertices of such that for any two vertic…
Vectorial solutions to list multicoloring problems on graphs
Yves Aubry, Jean-Christophe Godin, Olivier Togni
For a graph with a given list assignment on the vertices, we give an algebraical description of the set of all weights such that is -colorable, called permis…