Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2308.15588 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918531782672384 |
|---|---|
| author | Jing, Guangming |
| author_facet | Jing, Guangming |
| contents | Let $Δ(G)$ and $χ'(G)$ be the maximum degree and chromatic index of a graph $G$, respectively. Appearing in different forms, Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) made the following conjecture: Every multigraph $G$ satisfies $χ'(G) \le \max\{ Δ(G) + 1, Γ(G) \}$, where $Γ(G) = \max_{H \subseteq G, |V(H)|\geq 2} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil$ is the density of $G$. In this paper, we present a polynomial-time algorithm for coloring any multigraph with $\max\{ Δ(G) + 1, Γ(G) \}$ colors, confirming the conjecture algorithmically. Since $χ'(G)\geq \max\{ Δ(G), Γ(G) \}$, this algorithm gives a proper edge coloring that uses at most one more color than the optimum. As determining the chromatic index of an arbitrary graph is $NP$-hard, the $\max\{ Δ(G) + 1, Γ(G) \}$ bound is best possible for efficient proper edge coloring algorithms on general multigraphs, unless $P=NP$. Related work of Chen, Hao, Yu, and Zang have also obtained an algorithm using similar high-level ideas; the present approach establishes a complete proof. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_15588 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Edge Coloring of Multigraphs Jing, Guangming Combinatorics Let $Δ(G)$ and $χ'(G)$ be the maximum degree and chromatic index of a graph $G$, respectively. Appearing in different forms, Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) made the following conjecture: Every multigraph $G$ satisfies $χ'(G) \le \max\{ Δ(G) + 1, Γ(G) \}$, where $Γ(G) = \max_{H \subseteq G, |V(H)|\geq 2} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil$ is the density of $G$. In this paper, we present a polynomial-time algorithm for coloring any multigraph with $\max\{ Δ(G) + 1, Γ(G) \}$ colors, confirming the conjecture algorithmically. Since $χ'(G)\geq \max\{ Δ(G), Γ(G) \}$, this algorithm gives a proper edge coloring that uses at most one more color than the optimum. As determining the chromatic index of an arbitrary graph is $NP$-hard, the $\max\{ Δ(G) + 1, Γ(G) \}$ bound is best possible for efficient proper edge coloring algorithms on general multigraphs, unless $P=NP$. Related work of Chen, Hao, Yu, and Zang have also obtained an algorithm using similar high-level ideas; the present approach establishes a complete proof. |
| title | On Edge Coloring of Multigraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.15588 |