伪-Halin图的邻强边染色

On Adjacent Strong Edge Coloring of Pseudo-Halin Graphs with Δ(G)≥5

对图G(V,E),一正常k-边染色f称为图G(V,E)的k-邻强边染色,当且仅当对任意uv∈E(G),有f[u]≠f[v],其中f[u]={f(uw)｜uw∈E(G)},并称x′as(G)=min{k｜存在G的一k-ASEC}为G的邻强边色数.研究了Δ(G)≥5的伪-Halin图的邻强边色数,并通过归纳法证明了对Δ(G)=5的伪-Halin图G,有5≤x′as(G)≤6.如果E(G[VΔ])≠ ,则x′as(G)=6.并提出猜想:对｜V(G)｜≥6的连通图G(V,E)有Δ(G)≤x′as(G)≤Δ(G)+2.其中Δ(G)为G的最大度.

A proper k-edge coloring of graph G(V,E) is said to be a k-adjacent strong edge coloring(k-ASEC) of graph G(V,E) if every uv∈E(G) satisfy f[u]≠f[v],where f[u]=｛f(uw)｜uw∈E(G)｝,and x′_(as)(G)=min｛k｜k-ASEC｝ is called the adjacent strong edge chromatic number.The x′_(as)(G) of Pseudo-Halin graphs with Δ(G)≥5 is studied.Induction on p=｜V(G)｜ is used to prove that for Pseudo-Halin graph G of Δ(G)=5,have 5≤x′_(as)(G)≤6,and x′_(as)(G)=6 if E(G[V_Δ])≠0/,and give out a conjecture:for any connected graph G(V,E)(｜V(G)｜≥6) have Δ(G)≤x′_(as)(G)≤Δ(G)+2,where Δ(G) is the maximum degree of G.