A new tool for proving Vizing's Theorem

Alexandr Kostochka

doi:10.1016/j.disc.2014.02.021

A new tool for proving Vizing's Theorem

Alexandr Kostochka

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

The known proofs of the famous theorem of Vizing on edge coloring of (multi)graphs are not long but sophisticated. The main goal of this note is to present an auxiliary (multi)digraph that simplifies and facilitates proofs of it. The secondary goal is to use the approach for proofs of Vizing's Adjacency Lemma and the Andersen-Goldberg Theorem.

Original language	English (US)
Pages (from-to)	1-3
Number of pages	3
Journal	Discrete Mathematics
Volume	326
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2014.02.021
State	Published - Jul 6 2014

Keywords

Adjacency Lemma
Critical graphs
Edge coloring

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2014.02.021

Library availability

Discover UIUC Full Text

Cite this

@article{9d16e1f7704c4090ae2515ab1811088d,

title = "A new tool for proving Vizing's Theorem",

abstract = "The known proofs of the famous theorem of Vizing on edge coloring of (multi)graphs are not long but sophisticated. The main goal of this note is to present an auxiliary (multi)digraph that simplifies and facilitates proofs of it. The secondary goal is to use the approach for proofs of Vizing's Adjacency Lemma and the Andersen-Goldberg Theorem.",

keywords = "Adjacency Lemma, Critical graphs, Edge coloring",

author = "Alexandr Kostochka",

note = "Funding Information: I thank Douglas West, Xuding Zhu and Leonid Mel{\textquoteright}nikov for helpful discussions. Research is supported in part by NSF grant DMS-1266016 . ",

year = "2014",

month = jul,

day = "6",

doi = "10.1016/j.disc.2014.02.021",

language = "English (US)",

volume = "326",

pages = "1--3",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A new tool for proving Vizing's Theorem

AU - Kostochka, Alexandr

N1 - Funding Information: I thank Douglas West, Xuding Zhu and Leonid Mel’nikov for helpful discussions. Research is supported in part by NSF grant DMS-1266016 .

PY - 2014/7/6

Y1 - 2014/7/6

N2 - The known proofs of the famous theorem of Vizing on edge coloring of (multi)graphs are not long but sophisticated. The main goal of this note is to present an auxiliary (multi)digraph that simplifies and facilitates proofs of it. The secondary goal is to use the approach for proofs of Vizing's Adjacency Lemma and the Andersen-Goldberg Theorem.

AB - The known proofs of the famous theorem of Vizing on edge coloring of (multi)graphs are not long but sophisticated. The main goal of this note is to present an auxiliary (multi)digraph that simplifies and facilitates proofs of it. The secondary goal is to use the approach for proofs of Vizing's Adjacency Lemma and the Andersen-Goldberg Theorem.

KW - Adjacency Lemma

KW - Critical graphs

KW - Edge coloring

UR - http://www.scopus.com/inward/record.url?scp=84896533233&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896533233&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2014.02.021

DO - 10.1016/j.disc.2014.02.021

M3 - Article

AN - SCOPUS:84896533233

SN - 0012-365X

VL - 326

SP - 1

EP - 3

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

A new tool for proving Vizing's Theorem

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this