Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Grisot, Rémi
Université Côte d’Azur
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
On list coloring with separation of the complete graph and set system intersections Godin, Jean-Christophe; Grisot, Rémi; Togni, Olivier
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.5

Abstract

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)∩L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u)⊂L(u) and |φ(v)| = b for any vertex u and φ(u)∩φ(v)=∅ 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 Kn for some values of a, b and n, and prove bounds for the remaining values.
Co-Authors Godin, Jean-Christophe Togni, Olivier