网络图在频率分配中的应用

The Network Graphs With its Application in Frequency Assignment

如果图G有一个合理边着色,使得图G中任意两个相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。有一个准强边着色的图称为网络图(或准强边着色图)。使图G有一个准强边着色的最小色数称为网络图(或准强边着色图)的准强边色数,它被记为χ′qs(G)。讨论了网络图的分类问题和网络完全图的计数问题,提出并证明了下述网络图猜想(或准强边着色猜想):如果连通网络图有Δ(G)≥2,则网络图G的准强边色数有Δ(G)≤χ′qs(G)≤Δ(G)+3。

If a graph G has a proper edge coloring which makes the incident edge coloring sets between any two adjacent vertices in graph G are different from each other, such an edge coloring is said to be a quasi-strong edge coloring of graph. The graph with a quasi-strong edge coloring is said to be the network graph （or the quasi-strong edge coloring graph）. The minimum chromatic number, which makes the graph G have a quasi-strong edge coloring, is said to be the quasi-strong edge chromatic number of graphs, denoted by x＇qs （G）. This paper discusses the classification of network graphs and the enumeration problem of network complete graphs, and gives a network graph conjecture （or quasistrong edge coloring conjecture）： If the connected network graph G has △（G） ≥2, the quasi-strong edge chromatic number of network graphs has the property that △（G）≤x＇qi（G）≤△（G）＋3.