Přejít k obsahu


Packing chromatic number in outerplanar graphs with maxdegree 3

Citace:
HOLUB, P., GASTINEAU, N., TOGNI, O. Packing chromatic number in outerplanar graphs with maxdegree 3. Elgersburg, Germany, 2015.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: eng
Anglický název: Packing chromatic number in outerplanar graphs with maxdegree 3
Rok vydání: 2015
Autoři: RNDr. Přemysl Holub Ph.D. , Nicolas Gastineau Ph.D. , Olivier Togni Ph.D.
Abstrakt EN: A packing $k$-colouring of a graph $G$ is a mapping from the vertex set $V(G)$ to the set \{ 1,2,\dots, k \} (called colour set) such that any two vertices coloured with colour $i$ are at distance at least $i+1$. Then the packing chromatic number $\chi_{\rho}(G)$ of $G$ is the smallest integer $l$ such that there is a packing $l$-colouring of $G$. This concept was introduced by Goddard at el. under the name "broadcast colouring", but then the name was changed to "packing colouring" by Brešar et al. Sloper showed that a complete binary tree of arbitrary height at least three is packing $7$-colourable, while the infinite complete ternary tree is not packing colourable (i.e., we cannot colour vertices of the infinite complete ternary tree with a finite number of colours). It was shown that for paths and cycles, the packing chromatic number is at most $4$. Hence is it a natural question which classes of graphs with maximum degree $3$ can be packing colourable (i.e., for which classes of graphs with $\Delta=3$, the packing chromatic number is finite). Since the problem is very difficult even for the class of planar graphs with $\Delta=3$, we study the class of outerplanar graphs with $\Delta=3$. In this talk we present some subclasses of outerplanar graphs with $\Delta=3$, for which the packing chromatic number is finite.
Klíčová slova

Zpět

Patička