Description

Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from

$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$

with domain $V$ such

Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from

$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$

with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$

whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list

assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$

there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called

Reuse Permissions
  • 664.52 KB application/pdf

    Download count: 0

    Details

    Contributors
    Date Created
    • 2015
    Resource Type
  • Text
  • Collections this item is in
    Note
    • Partial requirement for: Ph. D., Arizona State University, 2015
      Note type
      thesis
    • Includes bibliographical references (pages 66-67)
      Note type
      bibliography
    • Field of study: Mathematics

    Citation and reuse

    Statement of Responsibility

    by Ran Wang

    Machine-readable links