38 citations · 61 across the 21 of their papers we have counts for
14 papers · 1 filter
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…
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…
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…
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…
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…
Every triangle-free induced subgraph of the triangular lattice is -choosable
Yves Aubry, Jean-Christophe Godin, Olivier Togni
A graph is -choosable if for any color list of size associated with each vertex, one can choose a subset of colors such that adjacent vertices are colored with d…
Choosability of a weighted path and free-choosability of a cycle
Yves Aubry, Jean-Christophe Godin, Olivier Togni
A graph with a list of colors and weight for each vertex is -colorable if one can choose a subset of colors from for each vertex , suc…