Gradus
VOL 3, NO 1 (2016): SPRING (APRIL)
A kiegészített szomszédsági komplexus vizsgálata
A study of extended neighborhood complex
Abstract
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).
Keywords
Kulcsszavak: lexikografikus szorzat, szomszédsági komplexus, homotópia típus,
Keywords: lexicographic product, neighborhood complex, homotopy type,
References
| [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. |