Volume 22, No 2, 2015, P. 17-26
UDC 519.718
V. G. Vizing
On coloring problems for the two-season multigraphs
Abstract:
It is supposed that there are two moments of time called seasons in which a multigraph can have various sets of edges. Such multigraphs are called two-season. In coloring vertices or edges every object is colored in one season. Some bounds on two-season chromatic number are given and the exact algorithm for the minimal edge coloring of a bipartite two-season multigraph is presented.
Bibliogr. 3.
Keywords: two-season multigraph, two-season coloring.
DOI: 10.17377/daio.2015.22.470
Vadim G. Vizing 1
1. Apt. 26, 18/2 Varnenskaya St.,
165070 Odessa, Ukraine
å-mail: vizing@paco.net
Received 22 December 2014
Revised 16 February 2015
References
[1] V. G. Vizing, On bases of vertices of a two-season directed graph, in Doklady Odesskogo seminara po diskretnoi matematike (Doklady of Odessa Seminar on Discrete Mathematics), Vol. 15, pp. 13–16, Astroprint, Odessa, 2014.[2] M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, No. 3, 237–267, 1976.
[3] D.König, Über Graphen und ihre Anvendung auf Determinantentheorie und Mengenlehre, Math. Ann., 77, No. 4, 453–465, 1916.
