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)
- Institution
- 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.
On the Choosability of Some Graphs
PDF (Portable Document Format)
226 KB
Created on 2/19/2023
Views: 99
Additional Information
- Publication
- Language: English
- Date: 2015
- Keywords
- List coloring, chromatic-choosable, cartesian product