On forbidden subdivision characterizations of graph classes
type: Item
instance of: scholarly article
title: On forbidden subdivision characterizations of graph classes
zbMATH Open document ID: 1151.05038
author: Zdeněk Dvořák
published in: European Journal of Combinatorics
publication date: 2008-05-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5280770
zbMATH Keywords: \(t\)-subdivision
zbMATH Keywords: acyclic proper coloring
zbMATH Keywords: acyclic chromatic number
zbMATH Keywords: arrangeability
zbMATH Keywords: greatest reduced average density
zbMATH Keywords: game chromatic number
zbMATH Keywords: graph classes
reviewed by: Alberto Cavicchioli
MaRDI profile type: Publication
full work available at URL: j.ejc.2007.05.008
OpenAlex ID: W2118815975
cites work: Coloring with no 2-colored \(P_4\)'s
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: On acyclic colorings of planar graphs
cites work: Graphs with linearly bounded Ramsey numbers
cites work: A bound for the game chromatic number of graphs
cites work: Q4116466
cites work: Q5692719
cites work: Fraternal augmentations, arrangeability and linear Ramsey numbers
cites work: Grad and classes with bounded expansion. I: Decompositions
cites work: Grad and classes with bounded expansion. II: Algorithmic aspects
cites work: Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
cites work: Radius two trees specify χ‐bounded classes
cites work: Orderings on graphs and game coloring number
cites work: On the Chromatic Number of Subgraphs of a Given Graph
cites work: Q5689012
cites work: Q4667626
DOI: 10.1016/J.EJC.2007.05.008
description: scientific article; zbMATH DE number 5280770