Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2211.07150 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914660024844288 |
|---|---|
| author | Mizutani, Ryuhei |
| author_facet | Mizutani, Ryuhei |
| contents | Kőnig's edge-coloring theorem for bipartite graphs and Vizing's edge-coloring theorem for general graphs are celebrated results in graph theory and combinatorial optimization. Schrijver generalized Kőnig's theorem to a framework defined with a pair of intersecting supermodular functions. The result is called the supermodular coloring theorem.
This paper presents a common generalization of Vizing's theorem and a weaker version of the supermodular coloring theorem. To describe this theorem, we introduce intersecting 2/3-supermodular functions, which are extensions of intersecting supermodular functions. The paper also provides an alternative proof of Gupta's edge-coloring theorem using a special case of this supermodular version of Vizing's theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07150 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Supermodular Extension of Vizing's Edge-Coloring Theorem Mizutani, Ryuhei Combinatorics Kőnig's edge-coloring theorem for bipartite graphs and Vizing's edge-coloring theorem for general graphs are celebrated results in graph theory and combinatorial optimization. Schrijver generalized Kőnig's theorem to a framework defined with a pair of intersecting supermodular functions. The result is called the supermodular coloring theorem. This paper presents a common generalization of Vizing's theorem and a weaker version of the supermodular coloring theorem. To describe this theorem, we introduce intersecting 2/3-supermodular functions, which are extensions of intersecting supermodular functions. The paper also provides an alternative proof of Gupta's edge-coloring theorem using a special case of this supermodular version of Vizing's theorem. |
| title | Supermodular Extension of Vizing's Edge-Coloring Theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2211.07150 |