Choice numbers of graphs - Computer Science > Discrete MathematicsReportar como inadecuado

Choice numbers of graphs - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: A solution to a problem of Erd\H{o}s, Rubin and Taylor is obtained by showingthat if a graph $G$ is $a:b$-choosable, and $c-d > a-b$, then $G$ is notnecessarily $c:d$-choosable. The simplest case of another problem, stated bythe same authors, is settled, proving that every 2-choosable graph is also$4:2$-choosable. Applying probabilistic methods, an upper bound for the$k^{th}$ choice number of a graph is given. We also prove that a directed graphwith maximum outdegree $d$ and no odd directed cycle is $kd+1:k$-choosablefor every $k \geq 1$. Other results presented in this article are related tothe strong choice number of graphs a generalization of the strong chromaticnumber. We conclude with complexity analysis of some decision problems relatedto graph choosability.

Autor: Shai Gutner


Documentos relacionados