Your query: an = (778.05073)
Answers 1-1 (of 1)
[New query form]
778.05073
Le Van Bang
Perfect $k$-line graphs and $k$-total graphs. (English)
[J] J. Graph Theory 17, No.1, 65-73 (1993). [ISSN 0364-9024]
Let $L\sb k(G)$ be the graph with vertex set corresponding to the $k$- simplices (complete subgraphs on $k$ vertices) of the graph $G$, in which two vertices are adjacent if and only if the corresponding $k$-simplices have exactly $k-1$ vertices in common. It is called the $k$-line graph of $G$. Let $T\sb k(G)$ be the graph with vertex set corresponding to the $(k-1)$- and $k$-simplices of $G$ in which two vertices are adjacent if and only if either (i) among the corresponding simplices $S$ and $S'$ at least one is a $k$-simplex and $\vert S\cap S'\vert=k-1$, or (ii) both the corresponding simplices $S$ and $S'$ are $(k-1)$-simplices with $S\cup S'$ a $k$-simplex. It is called the $k$-total graph of $G$. The author proves that $k$-line graphs and $k$-total graphs without odd holes are Berge. Using well-known properties of minimal imperfect graphs due to Lovasz, Padberg and Tucker, he proves that 3-line graphs without odd holes and 3-total graphs without odd holes are perfect. Also, the validity of SPGC for $L\sb k(G)$ for $k\ge 4$ is reduced to the case of graphs $G$ with $\omega(G)=k+1$. Another open problem is to design efficient recognition algorithms for these graphs.
[ K.R.Parthasarathy (Madras) ]
- MSC 1991:
-
*05C75 Structural characterization of types of graphs
05C15 Chromatic theory of graphs and maps
05C60 Isomorphism problems (graph theory)
Keywords: perfect graph conjecture; $k$-line graph; $k$-total graph
Cited in Zbl. reviews...
[New query form]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.