hrvatski jezikClear Cookie - decide language by browser settings

Multicoloring of graphs to secure a secret

Vojković, Tanja; Vukičević, Damir; Zlatić, Vinko (2018) Multicoloring of graphs to secure a secret. Rad Hrvatske akademije znanosti i umjetnosti. Razred za matematičke, fizičke i kemijske znanosti. Matematičke znanosti, 22 (534). pp. 1-22. ISSN 1845-4100

PDF - Accepted Version - article
Download (262kB) | Preview


Vertex coloring and multicoloring of graphs are a well known subject in graph theory, as well as their applications. In vertex multicoloring, each vertex is assigned some subset of a given set of colors. Here we propose a new kind of vertex multicoloring, motivated by the situation of sharing a secret and securing it from the actions of some number of attackers. We name the multicoloring a highly a-resistant vertex k-multicoloring, where a is the number of the attackers, and k the number of colors. For small values a we determine what is the minimal number of vertices a graph must have in order to allow such a coloring, and what is the minimal number of colors needed.

Item Type: Article
Additional Information: Partial support of the Croatian Ministry of Science and Education is gratefully acknowledged. We acknowledge the Israel-Italian collaborative project NECST as well as support by the H2020 CSA Twinning project No. 692194.
Uncontrolled Keywords: Graph theory ; graph coloring ; multicoloring ; secret sharing
Subjects: NATURAL SCIENCES > Mathematics
NATURAL SCIENCES > Mathematics > Discrete and Combinatorial Mathematics
Divisions: Theoretical Physics Division
Project titleProject leaderProject codeProject type
Ruđer Bošković Institute: Twinning for a step forward of the Theoretical Physics Division-RBI-T-WINNINGFabrizio NESTI692194EK
Depositing User: Vinko Zlatić
Date Deposited: 29 Apr 2020 11:44
DOI: 10.21857/m3v76t6jky

Actions (login required)

View Item View Item


Downloads per month over past year

Increase Font
Decrease Font
Dyslexic Font