Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-088-MZ-s
Name:
Distinguishing graph coloring
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr Pilśniak Monika (pilsniak@agh.edu.pl)
Academic teachers:
dr Pilśniak Monika (pilsniak@agh.edu.pl)
Module summary

Problemy i rodzaje kolorowania 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
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MA2A_K01 Oral answer,
Test,
Essay,
Examination,
Activity during classes
Skills
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MA2A_W05, MA2A_W04, MA2A_U03, MA2A_W02, MA2A_U13, MA2A_U02 Oral answer,
Test,
Essay,
Examination,
Activity during classes
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę MA2A_K02, MA2A_U03, MA2A_U01, MA2A_W02, MA2A_U13, MA2A_K01, MA2A_U02, MA2A_U14 Oral answer,
Test,
Essay,
Examination,
Activity during classes
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia, matematyka dyskretna) w teorii grafów MA2A_U14, MA2A_W07, MA2A_U19, MA2A_U04, MA2A_U08 Oral answer,
Test,
Essay,
Examination,
Activity during classes
Knowledge
M_W001 zna wybrane zaawansowane pojęcia i twierdzenia teorii grafów (rozróżnianie wszystkich lub sąsiednich wierzchołków grafu przy pomocy różnych kolorowań czy znaczeń krawędzi i wierzchołów) MA2A_W05, MA2A_W04, MA2A_W02, MA2A_U13, MA2A_U02 Oral answer,
Test,
Essay,
Examination,
Activity during classes
M_W002 rozumie potrzebę wprowadzenia różnych sposobów kolorowań oraz zna przykłady zastosowań rozważanych kolorowań w informatyce MA2A_K05, MA2A_U14, MA2A_U04 Oral answer,
Test,
Essay,
Examination,
Activity during classes
M_W003 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy MA2A_W03, MA2A_K05, MA2A_W06 Examination,
Activity during classes
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
Others
E-learning
Social competence
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Skills
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + + - - - - - - - - -
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę + + - - - - - - - - -
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia, matematyka dyskretna) w teorii grafów + + - - - - - - - - -
Knowledge
M_W001 zna wybrane zaawansowane pojęcia i twierdzenia teorii grafów (rozróżnianie wszystkich lub sąsiednich wierzchołków grafu przy pomocy różnych kolorowań czy znaczeń krawędzi i wierzchołów) + + - - - - - - - - -
M_W002 rozumie potrzebę wprowadzenia różnych sposobów kolorowań oraz zna przykłady zastosowań rozważanych kolorowań w informatyce + + - - - - - - - - -
M_W003 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
Module content
Lectures:

WYKŁADY

1. Liczba chromatyczna grafu. Twierdzenie Brooksa (bd.). Kolorowanie właściwe krawędzi grafu. Twierdzenie Wizinga (bd.). Twierdzenie Kőniga (bd.) o indeksie chromatycznym grafu dwudzielnego. Totalne kolorowanie grafu i hipoteza Behzada-Wiznga.

2. Kolorowania właściwe totalne i rozróżnianie sąsiednich wierzchołków sumami (jako uogólnienie rozróżniania zbiorami). Dowód hipotezy Pilśnak-Woźniaka dla subkubicznych i dwudzielnych. Ogólne ograniczenie (bd.)

3. Rozróżnianie sąsiednich wierzchołków sumami – cd.: grafy z małym średnim stopniem, dowód metodą rozładunku.

4-5. Rozróżnianie sąsiednich wierzchołków sumami – cd.: kolorowania z list, dowód hipotezy ch’=χ’ dla grafów dwudzielnych, dowód metodą rozładunku z zastosowaniem kombinatorycznego twierdzenia Hilberta o zerach dla grafów planarnych.

6. Kolorowania niewłaściwe totalne i hipoteza 1-2. Dowód Kalkowskiego z żetonami. Hipoteza 1-2 dla digrafów ze stopniem zbalansowanym.

7. Hipoteza 1-2 dla digrafów ze stopniem wyjściowym. NP-zupełność problemu – zastosowanie w informatyce.

8. Rozróżnianie wierzchołków paletami (drogami długości jeden) według Burris-Schelpa.

9. Rozróżnianie wierzchołków kolorowymi drogami; ograniczenie typu Wizinga.

10-11. Automorfizmy grafów i ich przełamywanie kolorowaniami – zastosowanie kolorowań rozróżniających w informatyce. Rozróżniające kolorowanie właściwe krawędzi. Indeks i liczba rozróżniająca; ogólne górne ograniczenia; drzewa; iloczyny kartezjańskie.

12. Grafy nieskończone. Lemat Kőniga. Graf Rado. Twierdzenie Wizinga i twierdzenie Brooksa dla grafów nieskończonych.

13. Wartość indeksu rozróżniającego dla grafów spójnych dowolnie dużych, dla grafu z minimalnym stopniem nieskończonym, dla hiperkostki nieskończenie wymiarowej.

14. Wartość liczby rozróżniającej nieskończonego iloczynu kartezjańskiego, w szczególności potęg kartezjańskich.

15. Ograniczenie górne indeksów rozróżniających dla grafów subkubicznych.

Auditorium classes:

ĆWICZENIA AUDYTORYJNE

Rozwiązywanie problemów (głównie teoretycznych) dotyczących treści przekazywanych na kolejnych wykładach.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 161 h
Module ECTS credits 6 ECTS
Participation in lectures 30 h
Participation in auditorium classes 30 h
Realization of independently performed tasks 50 h
Preparation for classes 50 h
Examination or Final test 1 h
Additional information
Method of calculating the final grade:

Ocena końcowa (OK) jest średnią ważoną ocen z egzaminu (E) i zaliczenia ćwiczeń audytoryjnych (A):
OK = 2/3 x E + 1/3 x A ,
gdzie E jest średnią arytmetyczną ocen uzyskanych na egzaminie w kolejnych terminach, A jest średnią arytmetyczną ocen uzyskanych z ćwiczeń w kolejnych terminach. Uzyskanie pozytywnej oceny końcowej następuje po uzyskaniu pozytywnego wyniku z egzaminu poprzedzonego pozytywnym zaliczeniem ćwiczeń.
Warunkiem przystąpienia do egzaminu jest wcześniejsze uzyskanie zaliczenia z ćwiczeń. Warunkiem ubiegania się o zaliczenie ćwiczeń jest 80% obecności na ćwiczeniach.

Prerequisites and additional requirements:

Egzamin z Teorii Grafów.

Recommended literature and teaching resources:

1. O.Baudon, J. Bensmail, E.Sopena, An oriented version of the 1-2-3 Conjecture, Discuss. Math. Graph Theory 35 (2015), 141–-156.

2. M.Borowiecki, J.Grytczuk, M.Pilśniak, Coloring chip configurations on graphs and digraphs, Information Processing Letters 112 (2012) 1-4.

3. A.C.Burris, R.H.Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory 26(2) (1997), 73—82.

4. R.Diestel, Graph Theory, 5th Edition, Springer-Verlag, 2016

5. L.Ding, G.Wang, J.Wu, J.Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Theoret. Computer Sci. 609 (2016), 162—170.

6. R.Hammack, W.Imrich, S.Klavžar, Handbook of product graphs, Second edition, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011.

7. M.Pilśniak, M.Woźniak, On the total neighbor distinguishing index by sums, Graphs and Combinatorics (2015) 31:771–782.

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

1. M.Pilśniak, M.Woźniak, On the total neighbor distinguishing index by sums, Graphs and Combinatorics (2015) 31:771–782.

2. M.Borowiecki, J.Grytczuk, M.Pilśniak, Coloring chip configurations on graphs and digraphs, Information Processing Letters 112 (2012) 1-4.

Additional information:

None