Volume 22, No 2, 2015, P. 17-26

UDC 519.718
V. G. Vizing 
On coloring problems for the two-season multigraphs

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


[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.
 © Sobolev Institute of Mathematics, 2015