My Math Forum Graph theory : coloring edges

 Applied Math Applied Math Forum

 January 28th, 2011, 11:39 AM #1 Newbie   Joined: Jan 2011 Posts: 1 Thanks: 0 Graph theory : coloring edges Hello, here is a "funny" problem. This is not homework and I don't need urgent answer. Consider an integer n>1 and n colors. Take a complete graph and color the edges such that for any three distinct vertices, one color occurs exactly twice. What is the maximal possible number of vertices ? Easily, for n=2, this is a well-known thing (due to Euler I think) that we cannot color a 6-vertices complete graph with 2 colors without having a monochromatic triangle, so the answer is 5 when n=2. But even for n=3 this seems complicated. It is not difficult to see that n cannot be greater than 15, since if there are at least 16 vertices for 3 colors, then there is a color such that a vertex x is connected with at least 6 edges colored in the same way, and the 6 vertices of these edges form a complete graph colored with 2 colors, which is impossible. So far, this "proof" can be used to find an upper bound, but I have not obtained anything else on the problem. Could anyone tell me if this problem is known, solved, or have an idea to get additional result? Thanks by advance

 Tags coloring, edges, graph, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post avnerg Applied Math 0 September 18th, 2013 06:03 AM discretemath Applied Math 1 October 27th, 2012 08:10 PM restin84 Applied Math 4 April 4th, 2012 12:12 PM tolmachevroman Applied Math 1 June 1st, 2011 05:00 AM viktord Computer Science 3 May 2nd, 2009 01:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top