An equitable colouring of a balanced G-design (X, B) is a map φ∶ B → C such that ∣bi(x)−bj(x)∣ ≤ 1 for any x ∈ X and i,j, with i ≠ j, being bi(x) the number of blocks containing the vertex x and coloured with the colour i. A c-colouring is a colouring in which exactly c colours are used. A c-colouring of type s is a colourings in which, for every vertex x, all the blocks containing x are coloured exactly with s colours. A bicolouring, tricolouring or quadricolouring is an equitable colouring with s=2, s=3 or s=4. In this paper we consider systems of graphs consisting of a 4-cycle and a pendant edge. We call such a graph a 4-kite and we consider balanced 4-kite systems. In particular, we prove that c-bicolourings of balanced 4-kite systems exist if and only if c = 2, 3.

Equitable block colourings for systems of 4-kites

BONACINI, PAOLA;GIONFRIDDO, Mario;MARINO, LUCIA MARIA
2017

Abstract

An equitable colouring of a balanced G-design (X, B) is a map φ∶ B → C such that ∣bi(x)−bj(x)∣ ≤ 1 for any x ∈ X and i,j, with i ≠ j, being bi(x) the number of blocks containing the vertex x and coloured with the colour i. A c-colouring is a colouring in which exactly c colours are used. A c-colouring of type s is a colourings in which, for every vertex x, all the blocks containing x are coloured exactly with s colours. A bicolouring, tricolouring or quadricolouring is an equitable colouring with s=2, s=3 or s=4. In this paper we consider systems of graphs consisting of a 4-cycle and a pendant edge. We call such a graph a 4-kite and we consider balanced 4-kite systems. In particular, we prove that c-bicolourings of balanced 4-kite systems exist if and only if c = 2, 3.
4-kite, C4 + e, block-colourings, G-decomposition
File in questo prodotto:
File Dimensione Formato  
bonaciniAMS21-24-2017-1.pdf

non disponibili

Descrizione: Articolo
Tipologia: Versione Editoriale (PDF)
Dimensione 348.46 kB
Formato Adobe PDF
348.46 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11769/299629
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact