One-Palette n -Color Maximizability.
A graph is said to be One-Palette n -Color Maximizable (OPNCM) if and only if, given a palette of n colors, the maximum probability of obtaining a coloring containing identically-colored adjacent vertices occurs when all palettes are identical. Intuition fools many into believing that all graphs are OPNCM, but families of non-OPNCM graphs exist. By creating a C/C++ program that calculates and compares the probabilities of each non-redundant palette set to the one-palette set probability, Ramin Naimi and I have found many non-OPNCM graphs with corresponding palette set examples. We have conjectured that all complete bipartite graphs with at least six vertices are non-OP2CM (non-OPNCM with n = 2). Furthermore, we have constructed a number of graph transformations on a non-OP2CM graph that maintains its non-OP2CM property. Currently, analysis of families of non-OP2CM graphs has begun to reveal links to the effect of intersecting two even cycles at v vertices and e edges. One of our major conjectures proposes that all non-OP2CM may be constructed from applying a finite number of transformations to a finite number of minimals (non-OP2CM graphs where removing any edge will produce an OP2CM graph). Future work includes analysis of non-OPNCM graphs with higher orders of n and the interplay between n and the types of graph transformations that preserve its non-OPNCM property.
Pelayo, Roberto, "One-Palette n -Color Maximizability." (2001). URC Student Scholarship.
CARE (CAMP) Award