#### Title

N-maximizability of Theta-less Graphs

#### Document Type

Article

#### Publication Date

2002

#### 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.

#### Recommended Citation

Kirov, Radoslav, " N-maximizability of Theta-less Graphs" (2002). *URC Student Scholarship.*

https://scholar.oxy.edu/urc_student/1009

#### Advisor

R. Naimi

#### Department

math

#### Support

Howard Hughes Medical Institute Fellowship