Abstract | ||
---|---|---|
We show that depth first search can be used to give a proper coloring of connected signed graphs G using at most \(\Delta (G)\) colors, provided G is different from a balanced complete graph, a balanced cycle of odd length, and an unbalanced cycle of even length, thus giving a new, short proof to the generalization of Brooks’ theorem to signed graphs, first proved by Máčajová, Raspaud, and Škoviera. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/s11590-015-0962-8 | Optimization Letters |
Keywords | Field | DocType |
Signed graph, Chromatic number, DFS, Greedy coloring | Edge coloring,Discrete mathematics,Complete coloring,Combinatorics,Signed graph,Chordal graph,Brooks' theorem,Greedy coloring,1-planar graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
10 | 4 | 1862-4480 |
Citations | PageRank | References |
2 | 0.41 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tamás Fleiner | 1 | 241 | 27.45 |
Gábor Wiener | 2 | 64 | 10.65 |