The list distinguishing number of Kneser graphs
| Autor: | Sajith Padinhatteeri, Niranjan Balachandran |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Vertex (graph theory)
Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 05C15 05C25 05C76 05C80 Automorphism 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Kneser graph Combinatorics (math.CO) Mathematics |
| Zdroj: | Discrete Applied Mathematics. 236:30-41 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2017.10.006 |
| Popis: | A graph $G$ is said to be $k$-distinguishable if the vertex set can be colored using $k$ colors such that no non-trivial automorphism fixes every color class, and the distinguishing number $D(G)$ is the least integer $k$ for which $G$ is $k$-distinguishable. If for each $v\in V(G)$ we have a list $L(v)$ of colors, and we stipulate that the color assigned to vertex $v$ comes from its list $L(v)$ then $G$ is said to be $\mathcal{L}$-distinguishable where $\mathcal{L} =\{L(v)\}_{v\in V(G)}$. The list distinguishing number of a graph, denoted $D_l(G)$, is the minimum integer $k$ such that every collection of lists $\mathcal{L}$ with $|L(v)|=k$ admits an $\mathcal{L}$-distinguishing coloring. In this paper, we prove that $D_l(G)=D(G)$ when $G$ is a Kneser graph. 13 pages, no figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect