Triangle-free partial graphs and edge covering theorems

✍ Scribed by J. Lehel; Zs. Tuza

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 722 KB
• Volume: 39
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90040-1

✦ Synopsis

In Section 1 some lower bounds are given for the maximal number of edges of a (p -l)colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p -l)-colorable partiai graph with at least mT,.$(;) edges, where T,,p denotes the so called Turin number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and or. is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by p triangles and edges. In Section 3 related questions are examined.

We will consider only loopless graphs withlout multiple edg.zs. If G = (X, E) is a graph, then the edge set Fc E together with the spanned vertices define a partial graph of G which will be denoted by the same letter F for simplicity reasons.

KP stands for a p-clique (compiete graph on p vertices); K3 will be called a