On the chromatic numbers of signed triangular and hexagonal grids

2020/12/17 by Jacques, Fabien
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2012.09678

Abstract

A signed graph is a simple graph with two types of edges. Switching a vertex v of a signed graph corresponds to changing the type of each edge incident to v. A homomorphism from a signed graph G to another signed graph H is a mapping φ: V(G) → V(H) such that, after switching any number of the vertices of G, φ maps every edge of G to an edge of the same type in H. The chromatic number χ_s(G) of a signed graph G is the order of a smallest signed graph H such that there is a homomorphism from G to H. We show that the chromatic number of signed triangular grids is at most 10 and the chromatic number of signed hexagonal grids is at most 4.

Related

• The chromatic number of signed graphs with bounded maximum average degree
• On the signed chromatic number of some classes of graphs
• The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree
• The chromatic number of a signed graph
• Chromatic number of signed graphs with bounded maximum degree