Přejít k obsahu


Distance colouring of grids and trees

Citace: [] HOLUB, P. Distance colouring of grids and trees. 2009.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: eng
Anglický název: Distance colouring of grids and trees
Rok vydání: 2009
Autoři: RNDr. Přemysl Holub Ph.D.
Abstrakt CZ: Pojmem t-distanční chromatické číslo grafu rozumíme minimální počet barev potřebných k obarvení vrcholů grafu tak, že žádné dva vrcholy ve vzdálenosti nejvýše t nejsou obarveny stejnou barvou. V této prezentaci jsou uvedeny horní odhady pro t-distanční chromatické číslo d-rozměrných čtvercových sítí a stromů s daným maximálním stupněm.
Abstrakt EN: The t-distance chromatic number of a graph G is the smallest positive integer k such that all the vertices of G at distance apart at most t have distinct colours. In this talk we give some upper bounds on t-distance chromatic number of d-dimensional square lattice and of trees with given maximum degree.
Klíčová slova

Zpět

Patička