Geodesic
How to find overfull subgraphs in graphs with large maximum degree. II
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be a simple graph with $3\Delta (G) > |V|$. The Overfull Graph Conjecture states that the chromatic index of $G$ is equal to $\Delta (G)$, if $G$ does not contain an induced overfull subgraph $H$ with $\Delta (H) = \Delta (G)$, and otherwise it is equal to $\Delta (G) +1$. We present an algorithm that determines these subgraphs in $O(n^{5/3}m)$ time, in general, and in $O(n^3)$ time, if $G$ is regular. Moreover, it is shown that $G$ can have at most three of these subgraphs. If $2\Delta (G) \geq |V|$, then $G$ contains at most one of these subgraphs, and our former algorithm for this situation is improved to run in linear time.
DOI : 10.37236/1551
Classification : 05C15, 05C85, 05C75
Mots-clés : chromatic index, maximum degree, overfull graph, algorithm, regular graphs 
@article{10_37236_1551,
     author = {Thomas Niessen},
     title = {How to find overfull subgraphs in graphs with large maximum degree. {II}},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1551},
     zbl = {0970.05023},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1551/}
}
TY  - JOUR
AU  - Thomas Niessen
TI  - How to find overfull subgraphs in graphs with large maximum degree. II
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1551/
DO  - 10.37236/1551
ID  - 10_37236_1551
ER  - 
%0 Journal Article
%A Thomas Niessen
%T How to find overfull subgraphs in graphs with large maximum degree. II
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1551/
%R 10.37236/1551
%F 10_37236_1551
Thomas Niessen. How to find overfull subgraphs in graphs with large maximum degree. II. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1551

Cité par Sources :