Article ID Journal Published Year Pages File Type
1710703 Applied Mathematics Letters 2006 5 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
, ,