Department of Mathematics, Faculty of Science, University of Split, 21000 Split, Croatia

*e-mail:* `vukicevi@pmfst.hr`

Institut Ruđer Bošković, 10 000 Zagreb, Croatia

CRN Institute for Complex Systems, via dei Taurini 19, 00185 Rome, Italy

*e-mail:* `Vinko.Zlatic@irb.hr`

**Abstract.** 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.

**2010 Mathematics Subject Classification.**
05C82, 05C15, 68R10, 94A62.

**Key words and phrases.** Graph theory, graph coloring, multicoloring, secret sharing.

DOI: http://doi.org/10.21857/m3v76t6jky

**References:**

- C. L. Baber, An introduction to list colorings of graphs, Master’s thesis,
Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 2009.
- A. Bar-Noy, M. M. Halldórsson, G. Kortsarz, R. Salman and H. Shachnai,
*Sum multicoloring of graphs*, J. Algorithms**37**(2000), 422-450.

MathSciNet CrossRef - B. Bollobas, Modern Graph Theory, Springer, New York, 1998.

MathSciNet CrossRef - F. H. Clarke and R. E. Jamison,
*Multicolorings, measures and games on graphs*, Discrete Math.**14**(1976), 241-245.

MathSciNet CrossRef - P. Erdős, A. L. Rubin and H. Taylor,
*Choosability in graphs*, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium (ed. P.Z. Chinn, D. McCarthy), Humboldt State University, Calif. 1979, pp. 125-157.

MathSciNet - M. M. Halldórsson and G. Kortsarz,
*Multicoloring: Problems and techniques*, in: International Symposium on Mathematical Foundations of Computer Science (ed. J. Fiala), Proc. of MFCS 2004, Prague 2004, pp. 25-41.

MathSciNet CrossRef - M. M. Halldórsson and G. Kortsarz,
*Tools for multicoloring with applications to planar graphs and partial*, J. Algorithms*k*-trees**42**(2002), 334-366.

MathSciNet CrossRef - P. Formanowicz and K. Tanaś,
*A survey of graph coloring - its types, methods and applications*, Found. Comput. Decision Sci.**37**(2012), 223-238.

MathSciNet CrossRef - T. R. Jensen and B. Toft, Graph coloring problems, John Wiley and Sons, New Yersey, 2011.

MathSciNet - B. Toft and T. R. Jensen,
*25 pretty graph colouring problems*, Discrete Math.**229**(2001), 167-169

MathSciNet CrossRef - F. R. Vieira, J. F. de Rezende and V. C. Barbosa,
*Scheduling wireless links by vertex multicoloring in the physical interference mode*, Computer Networks**99**(2016), 125-133.

CrossRef