Conditional chromatic numbers with forbidden cycles Original Research Article

The conditional chromatic numberx(G, P) of a graph G with respect to a graphical property P is the minimum number of colors needed to color the nodes of G such that each color class induces a subgraph of G with property P. The conditional chromatic number with respect to various properties has been studied by numerous authors. We investigate x(G, P), where P is the property of having no cycle of length j for fixed j ≥ 3. We find the conditional chromatic number with forbidden cycles for graphs of large size and for all graphs with order at most six.