On the Choosability of Some Graphs

ECSU Author/Contributor (non-ECSU co-authors, if there are any, appear on document)
Julian A. D. Allagan , Associate Professor (Creator)
Elizabeth City State University (ECSU )
Web Site: https://www.ecsu.edu/academics/library/index.html

Abstract: Suppose ch(G) and X(G) denote, respectively, the choice number and the chromatic number of a graph G = (V;E). If ch(G) = (G) then G is said to be chromatic-choosable. Recently, Reed et al. proved a conjecture by Ohba that states that G is chromatic choosable whenever jV (G)j <= 2(G) + 1. Here, we present otherclasses of chromatic-choosable graphs that do not satisfy the hypothesis of the proven conjecture. Moreover, we give the upper bounds for the choice numbers of the Mycielski graphs and the cartesian product of any two graphs, in terms of a vertex-neighborhood condition.

Additional Information

Language: English
Date: 2015
List coloring, chromatic-choosable, cartesian product

Email this document to