Your query: an = (864.05032)
Answers 1-1 (of 1)
[New query form]
864.05032
Van Bang Le
Gallai graphs and their iteration behavior. (English)
[D] Berlin: TU Berlin, FB Math. 80 p. (1994).
The vertices of the Gallai graph $\Gamma(G)$ of a graph $G$ are the vertices of the line graph of $G$ and two of them are adjacent in $\Gamma(G)$, if they form an induced path in $G$. In one chapter, the author supplies a characterization of Gallai graphs and discusses their relevance for colouring problems [the author, Gallai graphs and anti-Gallai graphs, Discrete Math. 159, No. 1-3, 179-189 (1996; Zbl 864.05031 above)]. Several chapters deals with the behaviour of the operator $\Gamma$. In particular so-called $\Gamma$-mortal graphs are characterized in several ways [the author, Mortality of iterated Gallai graphs, Period. Math. Hung. 27, No. 2, 105-124 (1993; Zbl 797.05068)]. The more difficult problem of characterizing $\Gamma$-periodic graphs is attacked and solved for several classes of graphs, among them the class of locally finite graphs with bounded degrees. A central tool is the classification of IHC-graphs, that is graphs $G$ such that each induced cycle of length at least 4 in $\Gamma\sp t(G)$ $(t\ge 0)$ is homogeneous.
[ H.A.Jung (Berlin) ]
- MSC 1991:
-
*05C15 Chromatic theory of graphs and maps
05C75 Structural characterization of types of graphs
05C38 Paths and cycles
Keywords: Gallai graph; line graph; characterization; colouring; induced cycle
Citations: Zbl 864.05031; Zbl 797.05068
Cited in Zbl. reviews...
[New query form]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.