New chromatic numbers in open problems
New chromatic numbers in open problems
复制标题
开放问题中的新色数
DOI：
10.15330/ms.45.2.115-117
复制
发表时间：
2016
影响因子：
5.6
通讯作者：
I. Protasov
中科院分区：
文献类型：
--
作者：
I. Protasov
设G是一个有限连通图(顶点集V (G)，边集E(G))，具有路径度量d（d（u， V）是u和V之间最短路径的长度）。路径u0， u1，…对于图G和自然数r，我们定义r- pathe (G):=极大值p，使得对于E(G)的每一次r着色，都有一条长度为p的边色路径；r-pathV (G):=极大p，使得对于V (G)的每一次r着色，都有一条长度为p的顶点单色路径；r-diamE(G):=极大p，使得对于E(G)的每一次r着色，存在一条长度为p的边色测地线路径；r-diamV (G):=极大p，使得对于V (G)的每一个r着色，都有一条长度为p的顶点单色测地路径。用方向代替E(G)的着色，我们得到−−→path(G):=极大p，使得对于E(G)的任何方向，都有一条长度为p的有向路径；−−−→diam(G):=极大的p，使得对于E(G)的任何方向，都有一条长度为p的有向测地线路径。我们记得，色数χ(G)是最小的r，使得V (G)的r着色没有单色的入射顶点。若r≥χ(G)，则r- pathv (G) = 0。V (G)的每个r-着色定义了E(G)的自然r(r+1) 2 -着色：每条边都以其末端的颜色着色。若r(r+1) 2≥χ(G)，则r(r+1) 2 -pathE(G) = 1。看来，pathV (G)和pathE(G)之间没有直接的联系。对于图G，线形图LG是一个顶点集合E(G)的图，当且仅当对应的边在G中关联时，两个顶点关联。显然，r-pathV (LG)≥r-pathE(G)。
Let G be a finite connected graph (with the set of vertices V (G) and the set of edges E(G)) endowed with the path metric d (d(u, v) is the length of a shortest path between u and v). A path u0, u1, . . . , un is geodesic if d(u0, vn) = n. The diam(G) is the maximal distance between two vertices of G. For a graph G and a natural number r, we define r-pathE(G) :=maximal p such that, for every r-coloring of E(G), there is an edgemonochrome path of length p; r-pathV (G) :=maximal p such that, for every r-coloring of V (G), there is a vertexmonochrome path of length p; r-diamE(G) :=maximal p such that, for every r-coloring of E(G), there is an edgemonochrome geodesic path of length p; r-diamV (G) :=maximal p such that, for every r-coloring of V (G), there is a vertexmonochrome geodesic path of length p. Replacing colorings of E(G) with orientations, we get −−→ path(G) :=maximal p such that, for any orientation of E(G), there is a directed path of length p; −−−→ diam(G) :=maximal p such that, for any orientation of E(G), there is a directed geodesic path of length p. We recall that the chromatic number χ(G) is the minimal r such that there is an r-coloring of V (G) with no monochrome incident vertices. If r ≥ χ(G) then r-pathV (G) = 0. Each r-coloring of V (G) define the natural r(r+1) 2 -coloring of E(G): each edge is colored in colors of its ends. If r(r+1) 2 ≥ χ(G) then r(r+1) 2 -pathE(G) = 1. It seems, there are no direct correlation between pathV (G) and pathE(G). For a graph G, the line graph LG is a graph with the set of vertices E(G) in which two vertices are incident if and only if corresponding edges are incident in G. Clearly, r-pathV (LG) ≥ r-pathE(G).