Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Winding number and circular 4-coloring of (signed) graphs

Abstract : Concerning the recent notion of circular chromatic number of signed graphs, we introduce a bipartite analogue of the generalized Mycielski graphs, denoted BM k,2k−1 , having the following properties. It has k(2k − 1) + 1 vertices, its shortest negative cycle is of length 2k and its circular chromatic number is 4. In the course of proving our result, we also obtain a simpler proof of the fact that the generalized Mycielski graph M ℓ (C 2k+1) has circular chromatic number 4. The proof has the advantage that it illuminates, in an elementary manner, the strong relation between algebraic topology and graph coloring problems.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Reza Naserasr Connect in order to contact the contributor
Submitted on : Sunday, November 6, 2022 - 12:09:40 AM
Last modification on : Wednesday, November 9, 2022 - 4:09:06 AM


Generalized Mycielski 1Nov 202...
Files produced by the author(s)


  • HAL Id : hal-03840738, version 1



Reza Naserasr. Winding number and circular 4-coloring of (signed) graphs. 2022. ⟨hal-03840738⟩



Record views


Files downloads