Teorija grafov

Prirejanja in faktorji (min-max izreki, neodvisne množice in pokritja, Tuttov izrek o 1-faktorju)
Povezanost (struktura 2-povezanih in k-povezanih grafov, dokaz in uporabe Mengerjevih izrekov)
Barvanja grafov (meje, dokaz Brooksovega izreka, struktura k-kromatičnih grafov, Turanov izrek, kromatični polinom, tetivni grafi)
Ravninski grafi (dualni graf, izrek Kuratowskega, konveksne vložiitve, barvanja ravninskih grafov, prekrižno število)
Predavatelj izbere še eno izmed naslednjih tem: barvanja povezav in graf povezav, hamiltonski grafi, popolni grafi, ekstremalni problemi, dominacija v grafih, simetrijske lastnosti grafov II.

R. Diestel: Graph Theory, 3. izdaja, Springer, Berlin, 2005.
A. Bondy, U.S.R. Murty: Graph Theory, 2. izdaja, Springer, Berlin, 2008.
D. West: Introduction to Graph Theory, 2. izdaja, Prentice Hall, Upper Saddle River, 2005.
R. J. Wilson, M. Watkins: Uvod v teorijo grafov, DMFA Slovenije, Ljubljana, 1997.

Študent poglobi in razširi znanje teorije grafov. Spozna uporabnost grafov in omrežij na različnih področjih matematike ter možnosti za njihovo uporabo tudi v drugih vejah znanosti.

Znanje in razumevanje: Slušatelj poglobi znanje iz teorije grafov.
Uporaba: Grafi omogočajo matematično modeliranje različnih pojavov. Slušatelj se seznani z vrsto matematičnih rezultatov, ki opisujejo lastnosti grafov in tako omogočajo matematično analizo modelov, opisanih z grafi.
Refleksija: Povezovanje teoretičnih spoznanj s praktičnimi uporabami na primer v optimizaciji in pri programiranju. Sposobnost prepoznavanja problemov, ki jih lahko uspešno opišemo z grafi.
Prenosljive spretnosti – niso vezane le na en predmet: Sposobnost opisa problemov iz vsakdanjega življenja s pomočjo matematičnih struktur, še posebej z grafi. Sposobnost uporabe matematičnih orodij za reševanje problemov.

predavanja, vaje, domače naloge, konzultacije

Izpit iz vaj (pisni izpit)
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Primož Potočnik:
POTOČNIK, Primož. Tetravalent arc-transitive locally-Klein graphs with long consistent cycles. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 270-281. [COBISS-SI-ID 16862041]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of symbolic computation, ISSN 0747-7171, 2013, vol. 50, str. 465-477. [COBISS-SI-ID 16520537]
POTOČNIK, Primož. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2004, vol. 91, no. 2, str. 289-300. [COBISS-SI-ID 13087321]
Sandi Klavžar:
KLAVŽAR, Sandi, SHPECTOROV, Sergey. Convex excess in partial cubes. Journal of graph theory, ISSN 0364-9024, 2012, vol. 69, no. 4, str. 356-369. [COBISS-SI-ID 16243033]
BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas. Domination game and an imagination strategy. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]
KLAVŽAR, Sandi. On the canonical metric representation, average distance, and partial Hamming graphs. European journal of combinatorics, ISSN 0195-6698, 2006, vol. 27, no. 1, str. 68-73. [COBISS-SI-ID 13858905]
Riste Škrekovski:
GOVORČIN, Jelena, KNOR, Martin, ŠKREKOVSKI, Riste. Line graph operation and small worlds. Information processing letters, ISSN 0020-0190. [Print ed.], 2013, vol. 113, iss. 5-6, str. 196-200. [COBISS-SI-ID 16561497]
DVOŘÁK, Zdeněk, LIDICKÝ, Bernard, ŠKREKOVSKI, Riste. Randić index and the diameter of a graph. European journal of combinatorics, ISSN 0195-6698, 2011, vol. 32, iss. 3, str. 434-442. [COBISS-SI-ID 17410905]
KAISER, Tomáš, STEHLÍK, Matěj, ŠKREKOVSKI, Riste. On the 2-resonance of fullerenes. SIAM journal on discrete mathematics, ISSN 0895-4801, 2011, vol. 25, no. 4, str. 1737-1745. [COBISS-SI-ID 16244569]
Arjana Žitnik:
MILANIČ, Martin, PISANSKI, Tomaž, ŽITNIK, Arjana. Dilation coefficient, plane-width, and resolution coefficient of graphs. Monatshefte für Mathematik, ISSN 0026-9255, 2013, vol. 170, no. 2, str. 179-193. [COBISS-SI-ID 1024499540]
ŽITNIK, Arjana, HORVAT, Boris, PISANSKI, Tomaž. All generalized Petersen graphs are unit-distance graphs. Journal of the Korean Mathematical Society, ISSN 0304-9914, 2012, vol. 49, no. 3, str. 475-491. [COBISS-SI-ID 16217945]
JURIŠIĆ, Aleksandar, TERWILLIGER, Paul, ŽITNIK, Arjana. The Q-polynomial idempotents of a distance-regular graph. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2010, vol. 100, iss. 6, str. 683-690. [COBISS-SI-ID 15688537]