Loredana Afanasiev, an V, Fac. Matematica si Informatica, Matematica Aplicata
Sergiu Cataranciuc, dr., conf., cond. stiintific

Fie o familie de grafuri complete cu n virfuri fiecare . Daca atunci z se numeste virf de incleiere a grafurilor , iar p se numeste rangul virfului de incleiere. Virful, care nu este virf de incleiere a unor grafuri se numeste virf liber.
Fie , astfel incit . Familia tuturor astfel de grafuri o notam prin . Prin anii `70 ai secolului trecut matematicianul Paul Erdős a inaintat ipoteza conform careea orice graf poate fi colorat corect cu ajutorul a n culori. Incercari de a rezolva aceasta problema au fost intreprinse de catre mai multi matematicieni. Un sir de rezultate interesante in aceasta directie au fost obtinute de catre Iacob Ciobanu[1].
Teorema 1 [1]: Graful , toate virfurile de incleiere ale caruia au rangul 2, este unic si virfurile lui de incleiere pot fi colorate cu n culori, in cazul cind n este impar, si culori, cind n este par.
Teorema 2: Daca graful are toate virfurile de incleiere de rangul 2, atunci el este unic, si toate virfurile libere se coloreaza intr-o singura culoare, daca n este un numar par, si se coloreaza in n culori diferite daca n este un numar impar.
Teorema 3 [1]: Daca sau ,, atunci exista cel putin un graf cu toate virfurile de incleiere de rangul 3, astfel incit
Teorema 4: Daca , pentru p,, atunci exista un graf astfel incit toate virfurile de incleiere au rangul p si .

Bibliografie: Iacob Ciobanu “Probleme extremale combinatorii pe grafuri si aplicatiile lor”, 1995, teza pentru conferirea gradului stiintific de doctor in stiinte fizico-matematice