A tree T is felicitous if there is a labelling l of its vertices with distinct integers from the set {0,1,2,…,｜E(T)｜}, so that the induced edge labelling l′ defined by l′(e)=l(u)+l(v) mod ｜E(T)｜ for eac...A tree T is felicitous if there is a labelling l of its vertices with distinct integers from the set {0,1,2,…,｜E(T)｜}, so that the induced edge labelling l′ defined by l′(e)=l(u)+l(v) mod ｜E(T)｜ for each e=uv∈E(T), assigns each edge e a different label. In this paper, we constructively proved that more classes of trees are felicitous. In the end, we gave a conjecture that every lobster tree is felicitous.展开更多
A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy...A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.展开更多
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we...The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.展开更多
文摘A tree T is felicitous if there is a labelling l of its vertices with distinct integers from the set {0,1,2,…,｜E(T)｜}, so that the induced edge labelling l′ defined by l′(e)=l(u)+l(v) mod ｜E(T)｜ for each e=uv∈E(T), assigns each edge e a different label. In this paper, we constructively proved that more classes of trees are felicitous. In the end, we gave a conjecture that every lobster tree is felicitous.
基金the Science Foundation of the Education Department of Hebei Province (2005108).
文摘A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.
基金This work is partially supported by National Natural Science foundation of China Doctoral foundation of the Education Committee of China.
文摘The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.
