✦ LIBER ✦

Clique-transversal sets of line graphs and complements of line graphs

✍ Scribed by Thomas Andreae; Martin Schughart; Zsolt Tuza

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 704 KB
Volume: 88
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90055-7

No coin nor oath required. For personal study only.

✦ Synopsis

Andreae, T., M. Schughart and Z. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Mathematics 88 (1991) 11-20. 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 t,(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 t,(G).

Assuming that G has no isolated vertices it is shown that (i) z,(G) <n/2 for all connected line graphs with the exception of odd cycles, and (ii) r,(G) cn/2 for all complments 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 22. 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.

📜 SIMILAR VOLUMES

A common generalization of line graphs a

A common generalization of line graphs and clique graphs

✍ Erich Prisner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 664 KB

## Abstract Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a __k__‐edge of a graph we mean a complete subgraph with __k__ vertices or a clique with fewer than __k__ vertices. The __k__‐

On the number of distinct minimal clique

On the number of distinct minimal clique partitions and clique covers of a line graph

✍ Sean McGuinness; Rolf Rees 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 812 KB

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculab

Clique polynomials and independent set p

Clique polynomials and independent set polynomials of graphs

✍ Cornelis Hoede; Xueliang Li 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

This paper introduces two kinds of graph polynomials, clique polynomial and independent set polynomial. The paper focuses on expansions of these polynomials. Some open problems are mentioned.

Hamilton connectivity of line graphs and

Hamilton connectivity of line graphs and claw-free graphs

✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh

Graphs isomorphic to subgraphs of their

Graphs isomorphic to subgraphs of their line-graphs

✍ Douglas Bauer; Ralph Tindell 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 621 KB

## An emhdding of graph G into graph N is by definition an isomorphism OI G onto a subgraph of H. It is shown in this paper that every unicycle V embeds in its line-graph L(V), and that every other connected graph that embeds in its own line-graph may be constructed from such an embedded unicycle