2010/04/29 by Radoslav Kirov, Ramin Naimi, Kirov, Radoslav +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1004.5183
arxiv created 2010/04/29 · arxiv updated 2010/04/30
In 1990, Kostochka and Sidorenko proposed studying the smallest number of list-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 is minimized when identical n-color lists are assigned to all vertices of G. Kostochka and Sidorenko observed that all chordal graphs are n-monophilic for all n. Donner (1992) showed that every graph is n-monophilic for all sufficiently large n. We prove that all cycles are n-monophilic for all n; we give a complete characterization of 2-monophilic graphs (which turns out 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.