134:
can have its edges colored with at most (3/2)Δ colors (a tight bound, as a triangle with Δ/2 edges per side requires this many colors). Although Vizing's theorem is now standard material in many graph theory textbooks, Vizing had trouble publishing the result initially, and his paper on it appears
105:
in 1974, where he taught mathematics for many years at the
Academy for Food Technology (originally known as Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, "Odessa Technological Institute of Food Industry named after
512:. Pages 136–137 reproduce a 1995 letter from Vizing to Soifer concerning the formulation of the total coloring conjecture, that also includes some biographical detail about Vizing.
101:
there and earning a Ph.D. in 1966. In
Novosibirsk, he was a regular participant in A. A. Zykov's seminar in graph theory. After holding various additional positions, he moved to
692:
411:, Vizing states that he formulated the conjecture in 1964, but by the time it was published in 1968 Behzad had independently posed the same conjecture.
687:
74:
682:
506:
301:
Vizing, V. G. (1974), "Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph",
150:
conjecture (still unsolved) stating that the edges and vertices of any graph can together be colored with at most Δ + 2 colors,
122:, published in 1964, when Vizing was working in Novosibirsk, states that the edges of any graph with at most Δ edges per vertex can be
657:
441:
82:
667:
662:
496:
677:
525:
159:
98:
370:, Vizing mentions that his work was motivated by Shannon's theorem. For the triangle lower bound example, see e.g.
163:
194:
Great Silver Medal of the
Institute of Mathematics of the Siberian Department of the Russian Academy of Sciences
672:
350:
151:
90:
78:
142:
Vizing also made other contributions to graph theory and graph coloring, including the introduction of
652:
647:
255:
167:
182:
119:
54:
385:
Akademiya Nauk SSSR. Sibirskoe
Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudov
279:
31:
541:
396:
175:
502:
155:
107:
617:
Vizing has somewhat changed his research interests, from pure graph theory to schedule theory
577:
263:
23:
612:
589:
275:
228:
608:
585:
549:
271:
224:
73:
on March 25, 1937. His mother was half-German, and because of this the Soviet authorities
605:
The development of combinatorics in the USSR: a brief historical and mathematical survey
259:
565:
371:
171:
147:
127:
641:
349:"Vizing" may be the romanization of the phonetic transcription of the German surname
283:
143:
123:
58:
46:
267:
50:
470:
94:
131:
43:
521:
93:, but he left in 1962 without completing his degree. Instead, he returned to
554:(in Russian), A.P. Ershov Institute of Informatics Systems, pp. 164–173
581:
431:
181:
From 1976, Vizing stopped working on graph theory and studied problems of
126:
using at most Δ + 1 colors. It is a continuation of the work of
631:
57:
stating that the edges of any simple graph with maximum degree Δ can be
77:
in 1947. After completing his undergraduate studies in mathematics in
102:
86:
211:
Vizing, V. G. (1964), "On an estimate of the chromatic class of a
246:
Vizing, V. G. (1968), "Some unsolved problems in graph theory",
70:
39:
303:
Proc. 3rd All-Union Conf. Problems of
Theoretical Cybernetics
321:
Vizing, V. G. (1976), "Vertex colorings with given colors",
568:(1949), "A theorem on coloring the lines of a network",
185:
instead, only returning to graph theory again in 1995.
607:, Delphic Associates, Falls Church, VA, p. 35,
174:in graphs. He also proved a stronger version of
551:Parallel programs construction and optimization
544:[About Zykov's seminar in Novosibirsk]
312:
292:
237:
202:
469:Gutin, Gregory; Toft, Bjarne (December 2000),
8:
632:List of recent publications of Vadim Vizing
81:in 1959, he began his Ph.D. studies at the
535:
533:
61:with at most Δ + 1 colors.
16:Soviet Ukrainian mathematician (1937–2017)
392:
363:
478:European Mathematical Society Newsletter
38:; 25 March 1937 – 23 August 2017) was a
422:
342:
408:
367:
464:
462:
460:
458:
456:
7:
75:forced his family to move to Siberia
97:, working from 1962 to 1968 at the
693:Ukrainian people of German descent
542:"О семинаре Зыкова в Новосибирске"
391:in 1980 (the name given for it in
383:The full name of this journal was
14:
162:, and the 1974 definition of the
688:Russian people of German descent
471:"Interview with Vadim G. Vizing"
442:Sobolev Institute of Mathematics
83:Steklov Institute of Mathematics
268:10.1070/RM1968v023n06ABEH001252
178:that applies to list coloring.
154:(also unsolved) concerning the
49:known for his contributions to
498:The Mathematical Coloring Book
1:
683:Tomsk State University alumni
526:Mathematics Genealogy Project
548:, in Kasyanov, V. N. (ed.),
160:cartesian products of graphs
395:) and discontinued in 1991
99:Russian Academy of Sciences
709:
495:Soifer, Alexander (2008),
389:Metody Diskretnogo Analiza
540:Mel'nikov, L. S. (2008),
438:In memory of V. G. Vizing
315:
295:
240:
205:
164:modular product of graphs
146:, the formulation of the
35:
28:Вади́м Гео́ргиевич Визинг
27:
658:Ukrainian mathematicians
118:The result now known as
36:Вадим Георгійович Візінг
20:Vadim Georgievich Vizing
603:Goldberg, Mark (1983),
393:Gutin & Toft (2000)
364:Gutin & Toft (2000)
135:in an obscure journal,
668:Russian mathematicians
582:10.1002/sapm1949281148
130:, who showed that any
91:function approximation
79:Tomsk State University
663:Soviet mathematicians
199:Selected publications
166:as a way of reducing
53:, and especially for
678:Scientists from Kyiv
440:] (in Russian),
433:Памяти В. Г. Визинга
372:Colorful Mathematics
170:problems to finding
168:subgraph isomorphism
89:, on the subject of
501:, Springer-Verlag,
260:1968RuMaS..23..125V
152:Vizing's conjecture
69:Vizing was born in
566:Shannon, Claude E.
508:978-0-387-74640-1
387:. It was renamed
335:
334:
311:
310:
291:
290:
248:Uspekhi Mat. Nauk
236:
235:
156:domination number
108:Mikhail Lomonosov
700:
620:
619:
600:
594:
592:
576:(1–4): 148–151,
570:J. Math. Physics
562:
556:
555:
547:
537:
528:
519:
513:
511:
492:
486:
485:
475:
466:
451:
450:
449:
448:
430:Borodin, O. V.,
427:
412:
405:
399:
381:
375:
360:
354:
347:
330:
323:Diskret. Analiz.
313:
306:
293:
286:
238:
231:
217:Diskret. Analiz.
203:
120:Vizing's theorem
114:Research results
55:Vizing's theorem
37:
29:
708:
707:
703:
702:
701:
699:
698:
697:
673:Graph theorists
638:
637:
628:
623:
602:
601:
597:
564:
563:
559:
545:
539:
538:
531:
522:Vadim G. Vizing
520:
516:
509:
494:
493:
489:
473:
468:
467:
454:
446:
444:
429:
428:
424:
420:
415:
406:
402:
382:
378:
361:
357:
348:
344:
340:
331:
320:
307:
300:
287:
245:
232:
210:
201:
191:
176:Brook's theorem
172:maximum cliques
137:Diskret. Analiz
116:
67:
17:
12:
11:
5:
706:
704:
696:
695:
690:
685:
680:
675:
670:
665:
660:
655:
650:
640:
639:
636:
635:
634:and mathnet.ru
627:
626:External links
624:
622:
621:
595:
557:
529:
514:
507:
487:
452:
421:
419:
416:
414:
413:
400:
376:
355:
341:
339:
336:
333:
332:
325:(in Russian),
319:
317:
309:
308:
299:
297:
289:
288:
254:(6): 117–134,
250:(in Russian),
244:
242:
234:
233:
219:(in Russian),
209:
207:
200:
197:
196:
195:
190:
187:
148:total coloring
128:Claude Shannon
115:
112:
66:
63:
15:
13:
10:
9:
6:
4:
3:
2:
705:
694:
691:
689:
686:
684:
681:
679:
676:
674:
671:
669:
666:
664:
661:
659:
656:
654:
651:
649:
646:
645:
643:
633:
630:
629:
625:
618:
614:
610:
606:
599:
596:
591:
587:
583:
579:
575:
571:
567:
561:
558:
553:
552:
543:
536:
534:
530:
527:
523:
518:
515:
510:
504:
500:
499:
491:
488:
483:
479:
472:
465:
463:
461:
459:
457:
453:
443:
439:
435:
434:
426:
423:
417:
410:
409:Soifer (2008)
404:
401:
397:
394:
390:
386:
380:
377:
373:
369:
368:Soifer (2008)
365:
359:
356:
353:into Russian.
352:
346:
343:
337:
328:
324:
318:
314:
305:, p. 124
304:
298:
294:
285:
281:
277:
273:
269:
265:
261:
257:
253:
249:
243:
239:
230:
226:
222:
218:
214:
208:
204:
198:
193:
192:
188:
186:
184:
179:
177:
173:
169:
165:
161:
157:
153:
149:
145:
144:list coloring
140:
138:
133:
129:
125:
121:
113:
111:
109:
104:
100:
96:
92:
88:
84:
80:
76:
72:
64:
62:
60:
56:
52:
48:
47:mathematician
45:
41:
33:
25:
21:
616:
604:
598:
573:
569:
560:
550:
517:
497:
490:
481:
477:
445:, retrieved
437:
432:
425:
403:
388:
384:
379:
358:
345:
326:
322:
302:
251:
247:
220:
216:
212:
180:
141:
136:
117:
68:
51:graph theory
19:
18:
653:2017 deaths
648:1937 births
95:Novosibirsk
642:Categories
447:2018-03-10
418:References
183:scheduling
132:multigraph
284:250848148
223:: 25–30,
215:-graph",
65:Biography
44:Ukrainian
32:Ukrainian
362:In both
613:0757359
590:0030203
524:at the
484:: 22–23
351:Wiesing
276:0240000
256:Bibcode
229:0180505
124:colored
59:colored
24:Russian
611:
588:
505:
329:: 3–10
282:
274:
227:
189:Awards
103:Odessa
87:Moscow
40:Soviet
546:(PDF)
474:(PDF)
436:[
338:Notes
280:S2CID
503:ISBN
366:and
316:V76.
296:V74.
241:V68.
206:V64.
110:").
71:Kiev
42:and
578:doi
407:In
264:doi
158:of
85:in
644::
615:,
609:MR
586:MR
584:,
574:28
572:,
532:^
482:38
480:,
476:,
455:^
327:29
278:,
272:MR
270:,
262:,
252:23
225:MR
139:.
34::
30:,
26::
593:.
580::
398:.
374:.
266::
258::
221:3
213:p
22:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.