Graph Theory

Computer Science and Mathematics, Second Cycle
1 ali 2 year
first or second
core mandatory
slovenian, english
Hours per week – 1. or 2. semester:

There are no prerequisites.

Content (Syllabus outline)

Connectivity, structure of 3-connected graphs. Planar graphs, proof of Kuratowski theorem, Schnyder theorem. Spectral graph theory. Colorings and flows. Matchings and coverings, Tutte theorem. Metric graph theory, embeddings of metric spaces into graphs. Operations on graphs, graph products.

  • A. Bondy, U.S.R. Murty: Graph Theory, 2. izdaja, Springer, Berlin, 2008.
  • R. Diestel: Graph Theory, 3rd Edition, Springer, Berlin, 2005.- W. Imrich, S. Klavžar, D.F. Rall, Topics in Graph Theory, A K Peters, Wellesley, 2008.- M. Juvan, P. Potočnik: Teorija grafov in kombinatorika: primeri in rešene naloge, Društvo matematikov, fizikov in astronomov Slovenije, Ljubljana 2000, 173 str. - D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, Upper Sadle River, 2001.
Objectives and competences

Students deepen and expand the knowledge of graph theory. They learn applicability of graphs and networks in different fields of mathematics (combinatorics, linear algebra, group theory, partially ordered sets...) and possibilities for their applications in other fields of science.

Intended learning outcomes

Knowledge and understanding:
Students get acquainted in detail with the selected topics from graph theory. They learn about the latest results in the field and its applications in mathematics and other fields of science.

Learning and teaching methods

Lectures, exercises, homework, consultations, projects.


Continuing (homework, midterm exams, project work)
Final (written and oral exam)
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

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]