W pracy opisano wybrane właściwości szczególnego przypadku radiowego kolorowania grafów, zwanego kolorowaniem średnicowym. Podano zasadę działania algorytmu optymalnego kolorowania średnicowego i oszacowania liczby średnicowej grafu w przypadku ogólnym oraz dla ścieżek i cykli. Korzystając z podanego algorytmu, znaleziono dokładne wartości liczby średnicowej dla ścieżek i cykli niewielkiej długości, co pozwoliło na obalenie wcześniej stawianych w literaturze hipotez dotyczących wartości liczby średnicowej ścieżek. Wysunięto przypuszczenie, że udowodnione w pracy oszacowania górne dla ścieżek są dokładne.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język
- polski
- Rok wydania
- 2005
Źródło danych: MOSTWiedzy.pl - publikacja "Optymalne pokolorowania średnicowe dla wybranych klas grafów" link otwiera się w nowej karcie
