Module also offered within study programmes:
General information:
Name:
STRUCTURAL GRAPH THEORY
Course of study:
2019/2020
Code:
ZSDA-3-0190-s
Faculty of:
Szkoła Doktorska AGH
Study level:
Third-cycle studies
Specialty:
-
Field of study:
Szkoła Doktorska AGH
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polski i Angielski
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
prof. dr hab. Woźniak Mariusz (mwozniak@agh.edu.pl)
Dyscypliny:
Moduł multidyscyplinarny
Module summary

Rozszerzona wiedza o aktualnych trendach teorii grafów.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i śledzenia na bieżąco rozwoju teorii grafów i wie jak to robić SDA3A_K01, SDA3A_K03 Activity during classes,
Examination
Skills: he can
M_U001 Potrafi analizować problemy pojawiające się w teorii grafów pod kątem ich potencjalnych zastosowań, odkrywczości i elegancji. Potrafi zidentyfikować potencjalne trudności występujące przy rozwiązywaniu problemów. SDA3A_U02, SDA3A_U01 Activity during classes,
Examination
M_U002 Wie jakimi kryteriami kierować się przy wyborze metody dowodu; potrafi przy tym korzystać z właściwej literatury. SDA3A_U04, SDA3A_U02 Activity during classes,
Examination
Knowledge: he knows and understands
M_W001 Ma rozszerzoną wiedzę o aktualnych trendach teorii grafów a także o klasycznych metodach tej teorii. Rozumie mechanizm uogólnień prowadzący do nowych problemów i hipotez. Zna konkretne przykłady dotyczące rozwoju pewnych obszarów teorii grafów. SDA3A_W02 Activity during classes,
Examination
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i śledzenia na bieżąco rozwoju teorii grafów i wie jak to robić + + - - - - - - - - -
Skills
M_U001 Potrafi analizować problemy pojawiające się w teorii grafów pod kątem ich potencjalnych zastosowań, odkrywczości i elegancji. Potrafi zidentyfikować potencjalne trudności występujące przy rozwiązywaniu problemów. + + - - - - - - - - -
M_U002 Wie jakimi kryteriami kierować się przy wyborze metody dowodu; potrafi przy tym korzystać z właściwej literatury. + + - - - - - - - - -
Knowledge
M_W001 Ma rozszerzoną wiedzę o aktualnych trendach teorii grafów a także o klasycznych metodach tej teorii. Rozumie mechanizm uogólnień prowadzący do nowych problemów i hipotez. Zna konkretne przykłady dotyczące rozwoju pewnych obszarów teorii grafów. + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 104 h
Module ECTS credits 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Realization of independently performed tasks 43 h
Examination or Final test 1 h
Module content
Lectures (30h):

PL

1. Wprowadzenie do teorii grafów. Zanurzanie grafów w swoje dopełnienie. Specjalne własności permutacji pakujących.
Grafy bez małych cykli. Zanurzenia w grafy płaskie.

2. Pakowanie grafów. Warunki na stopnie i rozmiary grafów. Hipoteza Erdosa-Sos.

3. Pakowanie trzech grafów. Hipoteza o pakowaniu drzew. Pakowanie w grafy dwudzielne.

4. Kolorowania rozróżniające wierzchołki grafu. Różne sposoby rozróżniania. Hipoteza Barris-Schelpa. Tw. Balistera o rozkładzie na drogi Eulera.

5. Kolorowania rozróżniające wierzchołki sąsiednie. Twierdzenie Gyoriego-Palmera.

6. Hipoteza 1-2-3 oraz hipoteza 1-2. Algorytm Kalkowskiego

7. Skierowane wersje hipotezy 1-2 i 1-2-3.

8. Wersje rozgrywane i zrównoważone.

9. Automorfizmy a kolorowania. Wersja wierzchołkowa i krawędziowa parametrów rozróżniających.

10. Grafy nieskończone i ich automorfizmy.

11. Grafy dowolnie podzielne. Twierdzenie Bartha-Fourniera.

12. Inne warianty dowolnej podzielności. Związek z zagadnieniami rozróżniania.

13. Cykle w grafach. Problemy hamiltonowskie i pancykliczność. Spektrum długości cykli.

14. Grafy nasycone ze względu na daną własność. Elementy teorii grafów krawędziowo
maksymalnych.

EN

1. Introduction to graph theory. Embeddings of graphs. Self-complementary permutations. Graphs without small cycles.
Embeddings into planar graphs.

2. Packing of graphs. Conditions on degrees and sizes. Erdos-Sos conjecture.

3. Some special problems. Packing of three graphs. Tree Packing Conjecture. Packing into bipartite graphs.

4. Edge colorings distinguishing vertices of a graph. Distinct ways of distinguishing.
Barris-Schelp Conjecture. Balister’s Theorem on decomposition into Euler trails.

5. Colorings distinguishing neighbor vertices. Gyori-Palmer Theorem.

6. 1-2-3 Conjecture and 1-2 Conjecture. Kalkowski’s algorithm.

7. Directed versions of 1-2-3 Conjecture and 1-2 Conjecture.

8. Neighbor distinguishing game and equable colorings.

9. Automorphisms and colorings. Vertex and edge versions of distinguishing parameters

10. Infinite graphs and their automorphisms.

11. Arbitrarily partitionable (AP) graphs. Barth-Fournier Theorem.

12. On-line and recursively AP graphs.

13. Cycles in graphs. Hamiltonian and pancyclic graphs. Spectrum of cycle lengths.

14. Graphs saturated with respect to a given property. Some elements of theory of
size maximal graphs.

Auditorium classes (30h):

Program ćwiczeń zgodny z programem wykładu.

Additional information
Teaching methods and techniques:
  • Lectures: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Auditorium classes: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

wg wytycznych prowadzących ćwiczenia

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Method of calculating the final grade:

Ocena końcowa jest równa ocenie z egzaminu.

Grade from examination.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

wg wytycznych prowadzących ćwiczenia

Prerequisites and additional requirements:

Brak

No.

Recommended literature and teaching resources:

1. B. Bollobas, Extremal Graph Theory, Academic Press, London, 1978.

2. A. Marczyk, Cycles in graphs and related problems, Dissertationes Math. 454
(2008), 1-98.

3. D.B. West, Introduction to graph theory, Prentice Hall, 2001.

4. M. Woźniak, Packing of graphs, Dissertationes Math. CCCLXII
(1997), 1-78.

5. Preprinty z serii „Matematyka Dyskretna”

Scientific publications of module course instructors related to the topic of the module:

1.M.Woźniak I A.P.Wojda, Triple placement of graphs, Graphs and
Combinatorics 9 (1993), 85-91.
2.M.Woźniak, Embedding graphs of small size, Discrete Applied Math.
51 (1994), 233–241.
3.M.Woźniak, On the Erdos–Sos conjecture, J. Graph Theory 21 (2)
(1996), 229–234.
4.M.Woźniak, Packing of Graphs, Dissertationes Mathematicae 362 (1997), pp.78
5.J-F.Sacle and M.Woźniak, The Erdos-Sos conjecture for graphs without
C4, J. Combin. Theory, Series B 70 (2) (1997), 367–372.
6.C.Bazgan, A.Harkat-Benhamdine, H.Li and M.Woźniak, On the vertexdistinguishing proper edgecolorings
of graphs, J. Combin. Theory, Series B 75 (1999), 288–301.
7.C.Bazgan, H.Li and M.Woźniak, On the Loebl-Komlos-Sos conjecture,
J. Graph Theory, 34 (2000), 269–276.
8.M.Hornak and M.Woźniak, Decomposition of complete bipartite even
graphs into closed trails, Czechoslovak Math. Journal 53 (1) (2003),
127–134.
9.A.Marczyk i M.Woźniak, Cycles in hamiltonian graphs of prescribed
maximum degree, Discrete Math. 266 (2003), 321–326.
10.M. Woźniak, Packing two copies of a tree into planar graph, Opuscula
Math. 23 (2003), 95–97.
11.E. Flandrin, H. Li, A. Marczyk i M. Woźniak, A note on a generalization
of Ore’s condition, Graphs and Combin., 21 (2005), 213–216.
12.S. Cichacz, A. Gorlich, A. Marczyk, J. Przybyło i M. Woźniak, Arbitrarily
vertex decomposable caterpilars with four or five leaves, Discussiones
Mathematicae-Graph Theory, 26 (2) (2006), 291–305.
13.M. Hornak, Zs. Tuza i M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Applied
Math. 155 (11) (2007), 1420–1429.
14.J. Przybyło and M. Woźniak, On a 1,2 Conjecture, Discrete Math.
Theoretical Computer Science, 12 (1) (2010), 101–108.
15.J. Przybyło and M. Woźniak, Total weight choosability of graphs, Electronic
J. Combin., 18 (1) (2011), 1. 112.
16.M. Pilśniak, M. Woźniak, On packing of two copies of a hypergraph,
Discrete Math. Theoretical Computer Science, 13 (3) (2011), 67–74.
17.E. Flandrin, A. Marczyk, J. Przybyło, J-F.Sacle i M.Woźniak, Neighbor
Sum Distinguishing Index, Graphs and Combinatorics 29 (2013), 1329–
1336.
18.M. Hornak, R. Kalinowski, M. Meszka and M. Woźniak, Minimum
Number of Palettes in Edge Colorings, Graphs and Combinatorics 30
(2014), 619–626.
19.O. Baudon, J. Bensmail, J. Przybyło i M. Woźniak, On decomposing
regular graphs into locally irregular subgraphs, European Journal of
Combinatorics, 49 (2015), 90–104.
20.M. Pilśniak and M. Woźniak, On the Total-Neighbor-Distinguishing
Index by Sums, Graphs and Combinatorics 31 (3) (2015), 771-782.

Additional information:

None