Anti-Ramsey Numbers of Subdivided Graphs
Anti-Ramsey Numbers of Subdivided Graphs
复制标题
DOI：
10.1006/jctb.2001.2105
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
T. Jiang
中科院分区：
文献类型：
--
作者：
T. Jiang
给定一个正整数n和一个图族F，反Ramsey数f（n，F）是Kn的一个边染色中的最大颜色数，使得Kn中属于F的所有子图的边都没有不同的颜色. Turan数x（n，F）是不包含F的成员作为子图的n-顶点图的最大边数。埃尔多？s等人（1975年，在Colloq. Math. Soc. Janos Bolyai，第10卷，第10页）。633？643，North-Holland，Amsterdam）证明了对于所有的图H，f（n，H）？ex（n，H）=o（n ~ 2），其中H={H？e：e？E（H）}。我们加强了他们的结果，一类图中的每一个边缘是事件的度为2的顶点。我们证明f（n，H）？当H属于这个类时，ex（n，H）=O（n）。这是从一个新的上界f（n，H），我们证明了所有的图H和渐近确定某些图H的f（n，H）。
Given a positive integer n and a family F of graphs, the anti-Ramsey numberf(n, F) is the maximum number of colors in an edge-coloring of Kn such that no subgraph of Kn belonging to F has distinct colors on its edges. The Turan numberex(n, F) is the maximum number of edges of an n-vertex graph that does not contain a member of F as a subgraph. P. Erdo?s et al. (1975, in Colloq. Math. Soc. Janos Bolyai, Vol. 10, pp. 633?643, North-Holland, Amsterdam) showed for all graphs H that f(n, H)?ex(n, H)=o(n2), where H={H?e:e?E(H)}. We strengthen their result for the class of graphs in which each edge is incident to a vertex of degree two. We show that f(n, H)?ex(n, H)=O(n) when H belongs to this class. This follows from a new upper bound on f(n, H) that we prove for all graphs H and asymptotically determines f(n, H) for certain graphs H.