Seminár Ústavu informatiky

Prednáška

Some bounds on the generalised total chromatic number of degenerate graphs

doc. RNDr. Gabriel Semanišin, PhD.
Ústav informatiky, PF UPJŠ

27. septembra 2017 (streda) o 12:45
SJ2S07 (3.16T), PF UPJŠ

Abstrakt

The total generalised (P,Q)-colourings are colourings of the vertices and of the edges of graphs satisfying the following conditions:

  • each set of vertices of the graph which receive the same colour induces a graph possessing prescribed property P,
  • each set of edges of the graph which receive the same colour induces a graph possessing prescribed property Q, and
  • incident elements receive different colours.

In our contribution we shall deal with a specific situation when the properties P and Q are “to be k-degenerate”. Bounds for the least number of colours with which this can be done for all k-degenerate graphs are obtained. Moreover we shall discuss some applications for a communication is Wireless Sensor Networks.

References

  • F. Galčík, G. Semanišin, Centralized broadcasting in radio networks with k-degenerate reachability graphs, in: ITAT 2006 Information Technologies – Applications and Theory, Bystrá dolina, Slovakia, 2006, pp. 41–46.
  • I. Broere, G. Semanišin, Some bounds on the generalised total chromatic number of degenerate graphs, Inform. Proc. Letters 122 (2017) 30–33, http://dx.doi.org/10.1016/j.ipl.2017.02.008