The chromatic number of signed graphs with bounded maximum average degree
share
A signed graph is a simple graph with two types of edges: positive and negative 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 some of the vertices of G, φ maps every edge of G to an edge of H of the same type. 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. The maximum average degree mad(G) of a graph G is the maximum of the average degrees of all the subgraphs of G. We denote ℳ_k the class of signed graphs with maximum average degree less than k and 𝒫_g the class of planar signed graphs of girth at least g. We prove: χ_s(𝒫_7) ≤ 5, χ_s(ℳ_17/5) ≤ 10 which implies χ_s(𝒫_5) ≤ 10, χ_s(ℳ_4-8/q+3) ≤ q+1 with q a prime power congruent to 1 modulo 4.
READ FULL TEXT