Rad HAZU, Matematičke znanosti, Vol. 22 (2018), 1-22.

MULTICOLORING OF GRAPHS TO SECURE A SECRET

Tanja Vojković, Damir Vukičević and Vinko Zlatić

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: https://doi.org/10.21857/m3v76t6jky

References:

1. C. L. Baber, An introduction to list colorings of graphs, Master’s thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 2009.

2. 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

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

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

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

6. 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

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

8. 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

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

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

11. 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