Graph theory

There are no prerequisites.

Matchings and factors (min-max theorem, independent sets and coverings, Tutte's 1-factor theorem)
Graph connectvity (structure of 2-connected and k-connected graphs, Menger theorem and its applications)
Graph colorings (bounds of the chromatic number, structure of k-chromatic graphs, Turan's theorem, chromatical polynomial, chordal graphs)
Planar graphs (dual graph, Kuratowski's theorem, convex embedding, colorings of planar graphs, crossing number)
Instructor chooses an addition topic from the following list: edge colorings and line graphs, Hamiltonian graphs, perfect graphs, extremal graph problems, graph domination, symmetry properties of graphs 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.

Students will deepen and broaden their knowledge of graph theory, and learn about the usefulness of graphs and networks in different areas of mathematics and their potential use in other branches of science.

Knowledge and understanding:
Students deepen their knowledge of graph theory.

Application:
Graphs allow mathematical modeling of variety of phenomena. Students learn various mathematical results that describe properties of graphs and thus provide a mathematical analysis of the models described by graphs.

Reflection:
Integration of theoretical knowledge with practical applications such as optimization and programming. Ability to recognize problems that can be successfully described by graphs.

Transferable skills:
The ability to describe practical problems with the help of mathematical structures, in particular with graphs. The ability to use mathematical tools to solve problems.

lectures, exercises, homeworks, consultations

Written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of 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]