Winding number and circular 4-coloring of signed graphs - CNRS - Centre national de la recherche scientifique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Winding number and circular 4-coloring of signed graphs

Anna Gujgiczer
  • Fonction : Auteur
  • PersonId : 1268734
Rohini S
  • Fonction : Auteur
  • PersonId : 1268735
Taruni S
  • Fonction : Auteur
  • PersonId : 1268736

Résumé

Concerning the recent notion of circular chromatic number of signed graphs, for each given integer k we introduce two signed bipartite graphs, each on 2k2 − k + 1 vertices, having shortest negative cycle of length 2k, and the circular chromatic number 4. Each of the construction can be viewed as a bipartite analogue of the generalized Mycielski graphs on odd cycles, Mℓ(C2k+1). In the course of proving our result, we also obtain a simple proof of the fact that Mℓ(C2k+1) and some similar quadrangulations of the projective plane have circular chromatic number 4. These proofs have the advantage that they illuminate, in an elementary manner, the strong relation between algebraic topology and graph coloring problems.
Fichier principal
Vignette du fichier
CircularChormaticProjectivePlanar4-Face-30June2023.pdf (394.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03840738 , version 1 (06-11-2022)
hal-03840738 , version 2 (08-07-2023)

Identifiants

  • HAL Id : hal-03840738 , version 2

Citer

Reza Naserasr, Anna Gujgiczer, Rohini S, Taruni S. Winding number and circular 4-coloring of signed graphs. 2023. ⟨hal-03840738v2⟩
53 Consultations
94 Téléchargements

Partager

Gmail Facebook X LinkedIn More