Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1710703 | Applied Mathematics Letters | 2006 | 5 Pages |
Abstract
For a graph HH, f(H)f(H) is the smallest integer kk such that the join of HH with an empty graph EkEk of order kk is not |V(H)||V(H)|-choosable. It was conjectured that for a triangle-free graph GG, f(G)=n2μ(G)nn−2μ(G), where n=|V(G)|n=|V(G)| and μ(G)μ(G) is the cardinality of a maximum matching of graph GG [S. Gravier, F. Maffray, B. Mohar, On a list-coloring problem, Discrete Math. 268 (2003) 303–308]. We verify this conjecture in the case of forests, and propose some related problems.
Keywords
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Baoyindureng Wu, Li Zhang,