Some bounds on the generalised total chromatic number of degenerate graphs
doc. RNDr. Gabriel Semanišin, PhD.
Ústav informatiky, PF UPJŠ
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.
- 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