N-maximizability of Theta-less Graphs

Abstract

A graph G is said to be n-maximizable if and only if we get the smallest number of proper colorings when using identical n-lists for all vertices. First we prove that all cycles are n-maximizable for n>=3 (the n=2 case was already known). Then we tried to prove that all theta-less graphs, which are graphs which have at most two independent paths (i.e., with disjoint interiors) between any two vertices, are also n-maximizable. Although we are still working on a proof in the most general case, we can prove it for theta-less graphs build in a certain way. If a graph is n-maximizable, we can add a cycle or path to a vertex of degree 2 and the resulting graph is n-maximizable. Thus we can build chains of cycles. Also we prove that "bouquets" of cycles (a number of cycles sharing one and the same vertex) are n-maximizable.