Abstract | ||
---|---|---|
In this paper we show that the list chromatic index of the complete graph Kn is at most n. This proves the list-chromatic conjecture for complete graphs of odd order. We also prove the asymptotic result that for a simple graph with maximum degree d the list chromatic index exceeds d by at most 𝒪(d2/3√log d). |
Year | DOI | Venue |
---|---|---|
1997 | 10.1017/S0963548397002927 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
complete graph,odd order,maximum degree,new bounds,dependent set,weight k,list chromatic index,lower bound,asymptotic result,list-chromatic conjecture,simple graph,list-chromatic index,simple graphs,random binary vector | Discrete mathematics,Outerplanar graph,Combinatorics,Foster graph,Friendship graph,Petersen graph,Butterfly graph,Windmill graph,1-planar graph,Mathematics,Critical graph | Journal |
Volume | Issue | Citations |
6 | 3 | 32 |
PageRank | References | Authors |
3.22 | 13 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Roland Häggkvist | 1 | 32 | 3.22 |
Jeannette Janssen | 2 | 295 | 32.23 |