zbMATH — the first resource for mathematics

Clique-transversal sets of line graphs and complements of line graphs. (English) Zbl 0734.05077
Authors’ abstract: A clique-transversal set T of a graph G is a set of vertices of G such that T meets all maximal cliques of G. The clique- transversal number, denoted \(\tau_ c(G)\), is the minimum cardinality of a clique-transversal set. Let n be the number of vertices of G. We study classes of graphs G for which n/2 is an upper bound for \(\tau_ c(G)\). Assuming that G has no isolated vertices it is shown that (i) \(\tau_ c(G)\leq n/2\) for all connected line graphs with the exception of odd cycles, and (ii) \(\tau_ c(G)\leq n/2\) for all complements of line graphs with the exception of five small graphs. In addition, a closely related question is studied: call G weakly 2-colorable if its vertices can be colored with 2 colors such that G has no monochromatic maximal clique of size \(\geq 2\). It is proved that a connected line graph \(G=L(H)\) is weakly 2-colorable iff H has a 2-coloring of its edges without monochromatic triangles and H is not an odd cycle. Moreover it is shown that complements of line graphs are weakly 2-colorable, with the exception of nine small graphs.

05C99 Graph theory
Full Text: DOI
[1] Berge, C.; Duchet, P., Strongly perfect graphs, (), 57-61 · Zbl 0558.05037
[2] Bondy, A.; Murty, U.S.R., Graph theory with applications, (1976), MacMillan Press London · Zbl 1226.05083
[3] Chvátal, V., Perfectly ordered graphs, (), 63-65 · Zbl 0559.05055
[4] P. Erdős, T. Gallai and Z. Tuza, Covering the cliques of a graph with vertices, Discrete Math., to appear.
[5] Graham, R.L.; Rothschild, B.L.; Spencer, J.H., Ramsey theory, (1980), Wiley New York · Zbl 0455.05002
[6] Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A., 44, 207-228, (1987) · Zbl 0637.06001
[7] Lovász, L., Perfect graphs, (), 55-88
[8] Ravindra, G., Meyniel graphs are strongly perfect, J. combin. theory ser. B., 33, 187-190, (1982) · Zbl 0498.05055
[9] Tuza, Z., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.