Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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

Julien Bensmail 1 François Dross 2 Nacim Oijid 3, 4, 5 Éric Sopena 2 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
5 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
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 :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03355826
Contributor : Julien Bensmail Connect in order to contact the contributor
Submitted on : Tuesday, May 10, 2022 - 10:55:00 PM
Last modification on : Friday, June 24, 2022 - 3:18:00 PM

Files

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

Identifiers

Citation

Julien Bensmail, François Dross, Nacim Oijid, Éric Sopena. Generalising the achromatic number to Zaslavsky's colourings of signed graphs. Theoretical Computer Science, Elsevier, 2022, 923, pp.196-221. ⟨10.1016/j.tcs.2022.05.009⟩. ⟨hal-03355826v2⟩

Share

Metrics

Record views

63

Files downloads

29