The chromatic number of a graph is the minimum k such that the graph has a proper k-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are 2-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. This notion was first suggested by Grünbaum in 1973, but no specific name was given. We revive this notion by defining an H-avoidingk-coloring to be a proper k-coloring that forbids a bicolored subgraph H. When considering the class C of graphs with no F as an induced subgraph, it is not hard to see that every graph in C has bounded chromatic number if and only if F is a complete graph of size at most two. We study this phenomena for the class of graphs with no F as a subgraph for H-avoiding coloring. We completely characterize all graphs F where the class of graphs with no F as a subgraph has bounded H-avoiding chromatic number for a large class of graphs H. As a corollary, our main result implies a characterization of graphs F where the class of graphs with no F as a subgraph has bounded star chromatic number. We also obtain a complete characterization for the acyclic chromatic number.
This work was done during the 2nd Korean Early Career Researcher Workshop in Combinatorics. Ilkyoo Choi was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education ( NRF-2018R1D1A1B07043049 ), and also by Hankuk University of Foreign Studies Research Fund . Ringi Kim was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) ( NRF-2018R1C1B6003786 ). Boram Park was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) ( NRF-2018R1C1B6003577 ).
