Name
Abstract | ||
|---|---|---|
Given a graph G and an integer k, two players alternatively color the edges of G using k colors so that adjacent edges get different colors. The game chromatic index@g"g^'(G) is the minimum k for which the first player has a strategy that ensures that all edges of G get colored. The trivial bounds are @D(G)@?@g"g^'(G)@?2@D(G)-1, where @D(G) denotes the maximal degree of G. Lam, Shiu, and Xu and, independently, Bartnicki and Grytczuk asked whether there is a constant C such that @g"g^'(G)@?@D(G)+C for every graph G. We show that the answer is in the negative by constructing graphs G such that @g"g^'(G)=1.008@D(G) and @D(G)-~. On the other hand, we show that for every @m0 there is @e0 such that for any graph G with @D(G)=(1/2+@m)v(G), we have @g"g^'(G)@?(2-@e)@D(G), where v(G) denotes the number of vertices of G. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.05.026 | Theoretical Computer Science |
Keywords | Field | DocType |
k color,g. lam,random strategies � research supported in part by nsf grant dms-0401147,random strategies,edge coloring of graphs,integer k,game chromatic index,constant c,games on graphs,adjacent edge,minimum k,graphs g,graph g,different color,graph g. | Edge coloring,Graph,Mathematical economics,Mathematics | Journal |
Volume | Issue | ISSN |
407 | 1-3 | Theoretical Computer Science |
Citations | PageRank | References |
3 | 0.63 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| Tom Bohman | 2 | 250 | 33.01 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Oleg Pikhurko | 4 | 318 | 47.03 |