Research On The Restricted Colorings Of Graphs And Relative Problems

Graph colorings belong to classical graph theoretical problems. Graph coloring theory is very important in discrete mathematics, and has plenty of theoretical results and extensively practical applications. In the latest years, a lot of research papers appeared in the field of restricted colorings of graphs. In this paper, we study several problems on restricted colorings of graphs.T-coloring of graphs provides a model of researching the channel assignment problems. Tesman [116] and liu [74, 75] studied the T-set satisfying some conditions. In this paper, we generalize some results of them with the similar ways. On the other hand, Cozzens and Roberts [22] raised the problem of computing the T-edge span of non-perfect graphs where T = {0,1,2,..., k — 1}. Liu [73] studied this problem for odd cycles, and Hu, Juan and Chang [51] for C_n~d, the dth power of the n-cycle. In this paper, we continue to study the edge span of C_n~d and get some better results.List coloring of graphs is a generalization of general coloring of graphs. Ghebleh and Mahmoodian [36] extensively studied the unique list colorability about complete multipartite graphs, especially for unique 3-list colorability. They almost completely characterized the uniquely 3-list colorable complete multipartite graphs. In this paper, we prove that graph K2,3,4 is not uniquely 3-list colorable, and as a result we completely characterize the uniquely 3-list colorable complete multipartite graphs. On the other hand, Lih et al. [72] used the way of discharging to prove that every planar graph without 4-cycles and i-cycles for some i ∈ {5,6,7} is (3, l)*-choosable, when they studied the list improper colorings of plane graphs. This paper shows that if graph G is 2-connected, we may just use Euler's formula and the graph's structural...