Korzhik V. Minimal embeddings of complete graphs and 1-immersions of graphs in two-dimensional surfaces

Українська версія

Thesis for the degree of Doctor of Science (DSc)

State registration number

0510U000858

Thesis Registration Form

0510U000858.pdf

Applicant for

Specialization

  • 01.01.08 - Математична логіка, теорія алгоритмів і дискретна математика

06-12-2010

Specialized Academic Board

Д26.001.18

Essay

We give a more simple proof of the Map Color Theorem for nonorientable surfaces and construct exponentially many nonisomorphic minimal embeddings of every complete graph. The distance between two triangular embeddings of a complete graph is investigated. Using Steiner triple systems, we show that there exist nonorientable triangular embeddings of complete graphs with unboundedly large looseness. The 1-chromatic number of every surface is found up to 10. We find an infinite series of surfaces with known 1-chromatic number.

Read more

Files

aref.doc

aref.doc

dis.pdf

Similar theses

0421U102374

Skochko Volodymyr Mykhailovych

The growth of initial invertible automata

0521U101177

Varbanets Serhii Pavlovych

Method on exponential sums in theory of congruential generators of the pseudorandom numbers and asymptotic problems in number theory

0419U004313

Dudenko Marharyta

Metric bases of graphs

0416U004040

Bashova Nadezhda Petrovna

The classification and the calculation of the number of the topologies on the finite sets

0416U000249

Tran Thе Vinh

Applications of the Kloosterman sums in cryptography and coding