An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other han...An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.展开更多
A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V...A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.展开更多
Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem ...Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem was improved to k≤7 by Borodin et al.However,by permitting the existence of adjacent triangles except K4,for an arbitrary integer k≥5,there exists a planar graph without cycles of length from 5 to k such that G is not 3-colorable.Let d denote the minimum distance between two diamonds in G,where a diamond is the union of two adjacent triangles.In this paper,we prove that a planar graph G with d≥2 and without cycles of length from 5 to 18 is 3-colorable.The reader is invited to find the smallest integer k such that a planar graph G with d≥2 and without cycles of length from 5 to k is 3-colorable.展开更多
基金supported by the National Natural Science Foundation of China (Grants Nos. 61072139,61072106,61203303,61003198,61272279,and 61003199)
文摘An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.
基金the National Natural Science Foundation of China (No.19871036) the Qinglan talent Funds of Lanzhou Jiaotong University
文摘A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.
基金partially supported by National Nature Science Foundation of China(No 12361067)Nature Science Foundation of Guangxi(No.2024GXNSFAA010506)+1 种基金Guangxi college students’innovation and entrepreneurship project(S202410608013)School-level talent programs(2022KJQD04 and2023MDKJ001)
文摘Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem was improved to k≤7 by Borodin et al.However,by permitting the existence of adjacent triangles except K4,for an arbitrary integer k≥5,there exists a planar graph without cycles of length from 5 to k such that G is not 3-colorable.Let d denote the minimum distance between two diamonds in G,where a diamond is the union of two adjacent triangles.In this paper,we prove that a planar graph G with d≥2 and without cycles of length from 5 to 18 is 3-colorable.The reader is invited to find the smallest integer k such that a planar graph G with d≥2 and without cycles of length from 5 to k is 3-colorable.
