
arXiv: 2009.00287
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)|\le a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $φ$ of sets of integers to the vertices of $G$ such that $φ(u)\subset L(u)$ and $|φ(v)|=b$ for any vertex $v$ and $φ(u)\cap φ(v)=\emptyset$ for any edge $uv$. 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\ge 5$.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), choosability, Planar graphs; geometric and topological aspects of graph theory, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], outerplanar graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Mathematics, coloring, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), choosability, Planar graphs; geometric and topological aspects of graph theory, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], outerplanar graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Mathematics, coloring, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
