Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776973 | Discrete Mathematics | 2017 | 10 Pages |
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
Thomas Schweser, Michael Stiebitz,