My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
January 28th, 2011, 11:39 AM   #1
Joined: Jan 2011

Posts: 1
Thanks: 0

Graph theory : coloring edges

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
Nekochan is offline  

  My Math Forum > College Math Forum > Applied Math

coloring, edges, graph, theory

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
bipartite graph, vertices, edges and arithmetics discretemath Applied Math 1 October 27th, 2012 08:10 PM
Proof: inequality involving vertices and edges of a graph restin84 Applied Math 4 April 4th, 2012 12:12 PM
Graph with non-intersecting edges tolmachevroman Applied Math 1 June 1st, 2011 05:00 AM
quantity of edges if graph k-regular? viktord Computer Science 3 May 2nd, 2009 01:13 PM

Copyright © 2018 My Math Forum. All rights reserved.