On forbidden subdivision characterizations of graph classes (Q925035): Difference between revisions

Let \(G\) be a simple undirected graph. A graph \(G'= G^{(t)}\) is the \(t\)-subdivision of \(G\) if \(G'\) is obtained from \(G\) by replacing each edge by a path with exactly \(t\) internal vertices. Similarly, \(G'\) is a \(\leq t\)-subdivision of \(G\) if \(G'\) can be obtained from \(G\) by subdividing each edge by at most \(t\) vertices. The number of vertices may be different for each edge. A coloring of the vertices of \(G\) is proper if no two adjacent vertices have the same color. The minimum \(k\) such that \(G\) has a proper coloring by \(k\) colors is called the chromatic number of \(G\), denoted \(\chi(G)\). A proper coloring of \(G\) is acyclic if the union of each two color classes induces a forest, i.e., there is no cycle colored by two colors. The minimum \(k\) such that \(G\) has an acyclic coloring by \(k\) colors is called the acyclic chromatic number of \(G\), denoted \(\chi_a(G)\). The acyclic chromatic number of a graph is also related to several other graph parameters, as, for example, the arrangeability, the greatest reduced average density, the game chromatic number and a sequence of parameters related to the expansion of a graph. The author gives an exact characterization of graph classes whose acyclic chromatic number is bounded by a constant. Analogous characterizations are given for some of the above-mentioned parameters.