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. PŘEDNÁŠKA, POSTER eng Packing chromatic number in outerplanar graphs with maxdegree 3 2015 RNDr. Přemysl Holub Ph.D. , Nicolas Gastineau Ph.D. , Olivier Togni Ph.D. 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.

Zpět