
The Library
Game chromatic index of graphs with given restrictions on degrees
Tools
Beveridge, Andrew, Bohman, Tom, Frieze, Alan and Pikhurko, Oleg (2008) Game chromatic index of graphs with given restrictions on degrees. Theoretical Computer Science, Vol.407 (No.1-3). pp. 242-249. doi:10.1016/j.tcs.2008.05.026 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2008.05.026
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 indexView the MathML source 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 View the MathML source, where Δ(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 View the MathML source for every graph G. We show that the answer is in the negative by constructing graphs G such that View the MathML source and Δ(G)→∞. On the other hand, we show that for every μ>0 there is ε>0 such that for any graph G with Δ(G)≥(1/2+μ)v(G), we have View the MathML source, where v(G) denotes the number of vertices of G.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.407 | ||||
Number: | No.1-3 | ||||
Number of Pages: | 8 | ||||
Page Range: | pp. 242-249 | ||||
DOI: | 10.1016/j.tcs.2008.05.026 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | NSF | ||||
Grant number: | DMS-0701183, CCR-0502793, DMS-0457512 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |