Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty

Partitioning edges of a planar graph into linear forests and a matching

Autor
Pilipczuk, Michał
Kowalik, Łukasz
Czyżewska, Jadwiga
Bonamy, Marthe
Data publikacji
2023
Abstrakt (PL)

We show that the edges of any planar graph of maximum degree at most 9 can be partitioned into 4 linear forests and a matching. Combined with known results, this implies that the edges of any planar graph G of odd maximum degree ∆ ≥ 9 can be partitioned into (∆−1)/2 linear forests and one matching. This strengthens well-known results stating that graphs in this class have chromatic index ∆ [Vizing, 1965] and linear arboricity at most ⌈(Δ+1)/2⌉.

Słowa kluczowe EN
Combinatorics
Discrete Mathematics
Dyscyplina PBN
informatyka
Czasopismo
Journal of Graph Theory
Tom
104
Zeszyt
3
Strony od-do
659-677
ISSN
0364-9024
Licencja otwartego dostępu
Dostęp zamknięty