List Coloring and $n$-monophilic graphs - Mathematics > CombinatoricsReportar como inadecuado

List Coloring and $n$-monophilic graphs - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In 1990, Kostochka and Sidorenko proposed studying the smallest number oflist-colorings of a graph $G$ among all assignments of lists of a given size$n$ to its vertices. We say a graph $G$ is $n$-monophilic if this number isminimized when identical $n$-color lists are assigned to all vertices of $G$.Kostochka and Sidorenko observed that all chordal graphs are $n$-monophilic forall $n$. Donner 1992 showed that every graph is $n$-monophilic for allsufficiently large $n$. We prove that all cycles are $n$-monophilic for all$n$; we give a complete characterization of 2-monophilic graphs which turnsout to be similar to the characterization of 2-choosable graphs given by Erdos,Rubin, and Taylor in 1980; and for every $n$ we construct a graph that is$n$-choosable but not $n$-monophilic.

Autor: Radoslav Kirov, Ramin Naimi


Documentos relacionados