Article ID Journal Published Year Pages File Type
5776973 Discrete Mathematics 2017 10 Pages PDF
Abstract
A signed graph is a graph in which each edge is labeled with +1 or −1. A (proper) vertex coloring of a signed graph is a mapping ϕ that assigns to each vertex v∈V(G) a color ϕ(v)∈Z such that every edge vw of G satisfies ϕ(v)≠σ(vw)ϕ(w), where σ(vw) is the sign of the edge vw. For an integer h≥0, let Z2h={±1,±2,…,±h} and Z2h+1=Z2h∪{0}. Following Máčajová et al. (2016), the chromatic number χ(G) of the signed graph G is the least integer k such that G admits a vertex coloring ϕ with im(ϕ)⊆Zk. As proved in Máčajová et al. (2016), every signed graph G satisfies χ(G)≤Δ(G)+1 and there are three types of signed connected simple graphs for which equality holds. We will extend this Brooks' type result by considering graphs having multiple edges. We will also prove a list version of this result by characterizing degree choosable signed graphs. Furthermore, we will establish some basic facts about color critical signed graphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,