VOL 3, NO 1 (2016): SPRING (APRIL)


A kiegészített szomszédsági komplexus vizsgálata

A study of extended neighborhood complex

Osztényi József


Tetszoőleges G átlós gráfra az EN (G) kiegészített szomszédsági komplexus pontra összehúzható, míg az N (G[Km]) szomszéd- sági komplexus homotóp ekvivalens egy gömbcsokorral. Azt sejt- jük, hogy ez általában is igaz lesz. Azaz ha a G gráf az EN (G) komplexus pontra összehúzható, akkor az N (G[Km]) komplexus homotóp ekvivalens egy gömbcsokorral. Jelen cikkben az EN (G) komplexus pontra összehúzhatóságának feltételeit vizsgájuk.

For a chordal graph G the extended neighborhood complex EN (G) contractible, while the neighborhood complex N (G[Km]) homotopy equivalent to a wedge of spheres. We conjecture that this will also be true in general. If for the graph G the comp- lex EN (G) contractible, then N (G[Km]) homotopy equivalent to a wedge of spheres. In this note we study the conditions of cont- ractible of the EN (G).


Kulcsszavak: lexikografikus szorzat, szomszédsági komplexus, homotópia típus,

Keywords: lexicographic product, neighborhood complex, homotopy type,


[1] G. Bredon. Topology and geometry, volume 139 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997.
[2] P. Csorba. On the simple Z2-homotopy types of graph complexes and their simple Z2-universality. Canadian Mathematical Bulletin, 51(4):535–544, 2008.
[3] P. Csorba and J. Osztényi. On the topological lower bound for the multichromatic number. Disc-rete Mathematics, 310(8):1334–1339, 2010.
[4] G. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25:71–76, 1961.
[5] D. Geller and S. Stahl. The chromatic number and other parameters of the lexicographic product.Journal of Combinatorial Theory, 19:87–95, 1975.
[6] E. Gilbert. Unpublished technical memorandum. iu, 1972.
[7] M. Kneser. Aufgabe 300. Jber. Deutsch. Math. Verein., 55, 1955.
[8] D. N. Kozlov. Combinatorial algebraic topology, volume 21 of Algorithms and Computation inMathematics. Springer, Berlin, 2008.
[9] L. Lovász. Kneser’s conjecture, chromatic number and homotopy. Journal of CombinatorialTheory, 25(3):319–324, 1978.
[10] J. Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combina-torics and Geometry. Universitext. Springer, Heidelberg, 2nd printing edition, 2008.
[11] R. Opsut and F. Roberts. On the fleet maintenance, mobile radio frequency, task assignment,and traffic phasing problems, pages 479–492. Wiley, New York, 1981.
[12] S. Stahl. n-tuple colorings and associated graphs. Journal of Combinatorial Theory, 20:185–203, 1976.

Copyright (c) 2020 Gradus