Geodesic
Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3
Fábio Botler1 ; Maycon Sambinelli2 ; Fábio Botler ; Maycon Sambinelli
1Programa de Engenharia de Sistemas e Computaçao, Universidade Federal do Rio de Janeiro, Brazil
2Instituto de Matemática e Estatística, Universidade de Sao Paulo, Brazil
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 501-505 
Fábio Botler; Maycon Sambinelli; Fábio Botler; Maycon Sambinelli. Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 501-505. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a22/
@article{AMUC_2019_88_3_a22,
     author = {F\'abio Botler and Maycon Sambinelli and F\'abio Botler and Maycon Sambinelli},
     title = { Gallai's path decomposition conjecture for graphs with maximum {E-degree} at most 3},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {501--505},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a22/}
}
TY  - JOUR
AU  - Fábio Botler
AU  - Maycon Sambinelli
AU  - Fábio Botler
AU  - Maycon Sambinelli
TI  - Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 501
EP  - 505
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a22/
ID  - AMUC_2019_88_3_a22
ER  - 
%0 Journal Article
%A Fábio Botler
%A Maycon Sambinelli
%A Fábio Botler
%A Maycon Sambinelli
%T Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 501-505
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a22/
%F AMUC_2019_88_3_a22

Voir la notice de l'article provenant de la source Comenius University

A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most (n+1)/2. Seminal results toward its verification consider the graph obtained from G by removing its vertices with odd degree, which is called the E-subgraph of G. Lovász (1968) verified Gallai's Conjecture for graphs whose E-subgraphs consist of at most one vertex, and Pyber (1996) verified it for graphs whose E-subgraphs are forests. In 2005, Fan verified Gallai's Conjecture for graphs whose E-subgraphs are triangle-free and contain only blocks with maximum degree at most 3. Since then, no result was obtained regarding E-subgraphs. In this paper, we verify Gallai's Conjecture for graphs whose E-subgraphs have maximum degree at most 3.