Choosability with Separation of Cycles and Outerplanar Graphs

arXiv2009.00287MaRDI QIDQ6348140FDOQ6348140

Authors: Jean-Christophe Godin, Olivier Togni

Publication date: 1 September 2020

Abstract: 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) | l e a

for any vertex

v

and

| L (u) c a p L (v) | l e c

for any edge

u v

of

G

, there exists an assignment

v a r p h i

of sets of integers to the vertices of

G

such that

v a r p h i (u) s u b s e t L (u)

and

| v a r p h i (v) | = b

for any vertex

v

and

v a r p h i (u) c a p v a r p h i (v) = e m p t y s e t

for any edge

u v

. 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 g e 5

.

This page was built for publication: Choosability with Separation of Cycles and Outerplanar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348140)