Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles
Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles
复制标题
无单色三角形的边色完全图的正确顶点全循环性
DOI：
10.1016/j.dam.2019.03.011
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Yuan Jinjiang
中科院分区：
文献类型：
--
作者：
Chen Xiaozheng;Huang Fei;Yuan Jinjiang
在一个有边着色的图（G, c）中，设dc (v)为与顶点v相关的边的颜色个数，设δ c (G)为dc (v)在所有顶点v∈v (G)上的最小值。如果一个（G, c）的环的任意两个相邻的边具有不同的颜色，则称其为固有环。如果（G, c）的每个顶点都包含在一个长度为l的适当环中，且每个l≤l≤n，则称为n≥3个顶点上的（G, c）的边色图（G, c）为适当顶点-环。Fujita和Magnant推测，n≥3个顶点上的每个δ c (G)≥n+ 12的边色完全图都是适当顶点-环。我们证明了如果边缘彩色完全图没有单色三角形，这个猜想是成立的。
In an edge-colored graph (G, c), let d c (v) be the number of colors on the edges incident to vertex v and let δ c (G) be the minimum value of d c (v) over all vertices v∈ V (G). A cycle of (G, c) is called proper if any two adjacent edges of the cycle have distinct colors. An edge-colored graph (G, c) on n≥ 3 vertices is called properly vertex-pancyclic if each vertex of (G, c) is contained in a proper cycle of length l for every l with 3≤ l≤ n. Fujita and Magnant conjectured that every edge-colored complete graph on n≥ 3 vertices with δ c (G)≥ n+ 1 2 is properly vertex-pancyclic. We show that this conjecture is true if the edge-colored complete graph has no monochromatic triangles.