Article ID Journal Published Year Pages File Type
4652690 Electronic Notes in Discrete Mathematics 2008 6 Pages PDF
Abstract

Let G be a graph of order p. For every n≥p let f(n,G) be the minimum integer k such that for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors. Let F be a set of graphs. For every n≥3 let ext(n,F) be the maximum number of edges of a graph on n vertices with no subgraph isomorphic to an element of F. Here we study the relation between f(n,G) and ext(n,C(G)) when G is a graph with chromatic number 3 obtained by adding an edge (a chord) to a cycle, and C(G) is the set of cycles which are subgraphs of G. In particular, an upperbound and a lowerbound of f(n,G) are given; and in the case when G is the diamond (C4 with a chord), we prove that the supremum and infimum limits of are bounded by and respectively, and we conjecture that for every n≥4, f(n,G)=ext(n,{C3,C4})+2.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics