• Strona główna AGH
  • AGH Main Page
 
Szukaj w systemie LAB
grupa / kierunek:
Nauki ścisłe i przyrodnicze / Matematyka

Specjalne kolorowania grafów

Kierownik: prof. dr hab. Mariusz Woźniak
Jednostka wiodąca: Katedra Matematyki Dyskretnej, Zespół Teorii Grafów
Wydział Matematyki Stosowanej
Główni wykonawcy:
Sylwia Cichacz, Jakub Przybyło, Mariusz Woźniak
Cele ogólne badań:
Naszym celem jest kontynuacja oraz osiągnięcie postępu w badaniach nad kolorowaniem grafów wymuszającym nieregularności na ich wierzchołkach. Głównymi zagadnieniami są tu:
1. nieregularna liczba kolorująca grafu;
2. indeks chromatyczny rozróżniający punkty grafu;
3. siła nieregularności grafu;
4. totalna wierzchołkowa siła nieregularności grafu;
5. hipoteza 1,2.
Projekty w ramach których realizowany jest temat:
Promotorski grant doktorski Ministerstwa Nauki i Szkolnictwa Wyższego nr N N201 389134.
Najważniejsze uzyskane wyniki:
Wyznaczone zostały przez nas między innymi:
1. nieregularna liczba kolorująca dla grafów będących lasami liniowymi lub sumami cykli parzystych;
2. indeks chromatyczny rozróżniający punkty dla grafów będących lasami liniowymi lub sumami cykli parzystych;
3. ograniczenia liniowe ze względu na n/δ na siłę nieregularności grafu;
4. lepsze ograniczenia liniowe ze względu na n/d na siłę nieregularności grafów regularnych;
5. ograniczenia liniowe ze względu na n/δ oraz zależne od gęstości grafu na totalną wierzchołkową siłę nieregularności;
6. lepsze ograniczenia liniowe ze względu na n/d oraz zależne od gęstości grafu na totalną wierzchołkową siłę nieregularności grafów regularnych;
7. wartość parametru związanego z hipotezą 1,2 dla pewnych klas grafów, takich jak np. grafy dwudzielne, grafy pełne, grafy 3-kolorowalne, grafy 4-regularne;
8. ograniczenie górne wartości powyższego parametru dla grafów regularnych;
9. ograniczenia górne wartości powyższego parametru dla wszystkich grafów dane stałą lub funkcją zależną od liczby chromatycznej lub maksymalnego stopnia grafu.
Najważniejsze publikacje:
1. S. Cichacz, A. Görlich, A. Marczyk, J. Przybyło i M. Woźniak: „Arbitrarily vertex decomposable caterpillars with four or five leaves” – Discusiones Mathematicae Graph Theory, vol. 26 no.2 (2006) s.291-305,
2. S. Cichacz, J. Przybyło i M. Woźniak: „Irregular edge-colorings of sums of cycles of even lengths” – Australasian Journal of Combinatorics, vol. 40 (2008) s. 41-56,
3. J. Przybyło: „Irregularity strength of regular graphs”- Electron. J. Combin. 15 (2008), (1), #R82,
4. S. Cichacz, J. Przybyło i M. Woźniak: „Decompositions of pseudographs into closed trails of even sizes” - Preprint MD 021 (2006), http://www.ii.uj.edu.pl/preMD/index.php; zaakceptowane w Discrete Mathematics,
5. J. Przybyło i M. Woźniak: „1,2 Conjecture II” - Preprint MD 027 (2007), http://www.ii.uj.edu.pl/preMD/index.php,
6. S. Cichacz i J. Przybyło: „Vertex-distinguishing edge-colorings of sum of paths” - Preprint MD 027 (2007), http://www.ii.uj.edu.pl/preMD/index.php,
7. J. Przybyło: „A note on neighbour-distinguishing regular graphs total-weighting” - Preprint MD 031 (2007), http://www.ii.uj.edu.pl/preMD/index.php,
8. J. Przybyło: „Linear bound on the irregularity strength and the total irregularity strength of graphs” - Preprint MD 038 (2008), http://www.ii.uj.edu.pl/preMD/index.php.
Dane osoby kontaktowej:
Jakub Przybyło; tel. (012) 617 44 09; E-mail: przybylo@wms.mat.agh.edu.pl

data aktualizacji: 2008-07-11

All rights reserved (c) 2013 Akademia Górniczo-Hutnicza