On forbidden subdivision characterizations of graph classes
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.
- A bound for the game chromatic number of graphs
- Coloring with no 2-colored \(P_4\)'s
- Fraternal augmentations, arrangeability and linear Ramsey numbers
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Graphs with linearly bounded Ramsey numbers
- scientific article; zbMATH DE number 3540832 (Why is no real title available?)
- scientific article; zbMATH DE number 2159660 (Why is no real title available?)
- scientific article; zbMATH DE number 970807 (Why is no real title available?)
- scientific article; zbMATH DE number 2209736 (Why is no real title available?)
- On acyclic colorings of planar graphs
- On the Chromatic Number of Subgraphs of a Given Graph
- Orderings on graphs and game coloring number
- Radius two trees specify χ‐bounded classes
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Generalization of transitive fraternal augmentations for directed graphs and its applications
- Induced and weak induced arboricities
- Characterization of forbidden subgraphs for bounded star chromatic number
- A forbidden subgraph characterization of some graph classes using betweenness axioms
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Minimal separators in graph classes defined by small forbidden induced subgraphs
- Equitable partition of graphs into induced forests
- On nowhere dense graphs
- Distance-two coloring of sparse graphs
- 1-subdivisions, the fractional chromatic number and the Hall ratio
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
- Forbidden-minor characterization for the class of graphic element splitting matroids
- Colouring edges with many colours in cycles
- scientific article; zbMATH DE number 2159660 (Why is no real title available?)
- First order properties on nowhere dense structures
- Properties of large 2-crossing-critical graphs
- A unified approach to structural limits and limits of graphs with bounded tree-depth
- Graph sharing game and the structure of weighted graphs with a forbidden subdivision
- On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
- scientific article; zbMATH DE number 7731182 (Why is no real title available?)
- Hat Guessing Numbers of Strongly Degenerate Graphs
- Characterisations and examples of graph classes with bounded expansion
- Enumerations, forbidden subgraph characterizations, and the split-decomposition
- Oriented colouring graphs of bounded degree and degeneracy
- Injective edge colorings of degenerate graphs and the oriented chromatic number
- Acyclic colorings of graphs with obstructions
- Rank-width and tree-width of \(H\)-minor-free graphs
- First-order transductions of graphs (invited talk)
- Sublinear separators, fragility and subexponential expansion
This page was built for publication: On forbidden subdivision characterizations of graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q925035)
