An Introduction to Colored-independence in Graphs

摘要

This paper considers the concept of colored problems for graph parameters. Assuming one has a partition S = {S_1, S_2,..., S_t} of vertex set V(G) (that is, a t-coloring of V(G)), one seeks to optimize the order of a set S with a certain property such that S must contain either all or none of the elements of S_i, 1 ≤ i ≤ t. Here proper coloring are considered, and of interest is the partition that provides the minimum possible size of a maximum cardinality colored-independent set. Problems involving further restrictions on allowable partitions will also be introduced.