1-树图的邻强边染色

On The Adjacent Strong Edge Coloring of 1-Tree

中文关键词:  图  邻强边染色  邻强边色数.

英文关键词:graph  adjacent strong edge coloring  adjacent strong edge chromatic number.

中文摘要:

      图G的一k-正常边染色f若使得任意uv∈E(G)满足f[u]≠f[v],其中f[u]={f(uω)|uw∈E(G)},则称f为G的一k-邻强边染色,简称k-ASEC,并称χ_as(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.本文提出了邻强边染色猜想:对2-连通图G(V,E)(G(V,E)≠C₅),有△(G)≤χ_as(G)≤△(G)+2,并研究了1-树图的邻强边染色,证明了对△(G)≥4的1-树图G有△(G)≤χ_as<

英文摘要:

      Let G(V,E) be a graph. A k -proper edge coloring f is called a k -adjacent strong edge coloring of G(V,E) iff every uv∈ E(G) satisfies f[u] ≠ f[v], where f[u] = (f(uw) |uw∈E(G) }, is called k -ASEC for short, and χ_as(G) = min{k | There exists a k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper,we present a conjec- ture that for 2-connected graph G(V,E) (G(V,E) ≠ C₅),△ (G) ≤χ_as(G) ≤ △(G) + 2, and prove that for 1-tree graph with △(G)≥4 have △(G) ≤ χ_as(G) ≤ △(G)+1 and χ_as(G) = △(G)+1 iff E(G[V_△])≠φ,where V_△=(u|u∈V(G),d(u)=△(G)}.