Geodesic
Boundary classes of graphs for some recognition problems
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 85-94.

Voir la notice de l'article provenant de la source Math-Net.Ru

The class of all graphs in which every connected component is a tree with at most three leaves and the class of line graphs of this class are considered in the article. There is a series of well-known problems for which these classes are boundary classes. We study common properties of such problems. Namely, we prove a sufficient condition for the considered classes to be boundary classes. Using the obtained tool we add 8 new cases of given classes being boundary classes to known ones. Bibl. 10.
Keywords: extremal graph problems, computational complexity, boundary class. 
@article{DA_2009_16_2_a6,
     author = {D. S. Malyshev},
     title = {Boundary classes of graphs for some recognition problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {85--94},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Boundary classes of graphs for some recognition problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 85
EP  - 94
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/
LA  - ru
ID  - DA_2009_16_2_a6
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Boundary classes of graphs for some recognition problems
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 85-94
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/
%G ru
%F DA_2009_16_2_a6
D. S. Malyshev. Boundary classes of graphs for some recognition problems. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 85-94. http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/

[1] Alekseev V. E., Malyshev D. S., “Kriterii granichnosti i ego primeneniya”, Diskret. analiz i issled. operatsii, 15:6 (2008), 3–10

[2] Kharari F., Teoriya grafov, Mir, M., 1982, 301 pp.

[3] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theoret. Comp. Sci., 389 (2007), 219–236 | DOI | MR | Zbl

[4] Bodlaender H. L., “Dynamic programming on graphs with bounded treewidth”, Automata, languages and programming, Proc. (Tampere, 1988), Lect. Notes in Comp. Sci., 317, Springer-Verl., Berlin, 1988, 105–118 | MR

[5] Kloks T., “Treewidth, computations and approximations”, Lect. Notes in Comp. Sci., 842, Springer-Verl., Berlin, 1994, 211 | MR

[6] Lozin V. V., “Boundary classes of planar graphs”, Combinatorics, Probability and Computing, 17 (2008), 287–295 | DOI | MR | Zbl

[7] Lozin V. V., Rautenbach D., “On the band-, tree- and clique-width of graphs with bounded vertex degree”, SIAM J. Discrete Math., 18 (2004), 195–206 | DOI | MR | Zbl

[8] Middendorf M., Pfeiffer F., “On the complexity of the disjoint path problem”, Combinatorica, 13:1 (1993), 97–107 | DOI | MR | Zbl

[9] Roussopoulos N., “A $\max\{m,n\}$ algorithm for determining the graph $H$ from its line graph $G$”, Information Processing Letters, 2:4 (1973), 108–112 | DOI | MR | Zbl

[10] Scheffler P., A practical linear algorithm for vertex disjoint path in graphs with bounded treewidth, Technical report No 396, Department of Mathematics, Technische Universität Berlin, 1994, 21 pp.