Skip to Main content Skip to Navigation
Reports

Generalising the achromatic number to Zaslavsky's colourings of signed graphs

Abstract : The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number. This work takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. We here pursue this line of research, but with taking Zaslavsky's colourings as our notion of proper colourings. We study the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects.
Document type :
Reports
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03355826
Contributor : Julien Bensmail Connect in order to contact the contributor
Submitted on : Monday, September 27, 2021 - 3:30:17 PM
Last modification on : Saturday, December 4, 2021 - 3:07:37 AM

Files

achromatic-signed.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03355826, version 1
  • ARXIV : 2109.13627

Citation

Julien Bensmail, François Dross, Nacim Oijid, Éric Sopena. Generalising the achromatic number to Zaslavsky's colourings of signed graphs. [Research Report] Université côte d'azur; Université de Bordeaux; Université lyon 1. 2021. ⟨hal-03355826⟩

Share

Metrics

Record views

37

Files downloads

26