A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for...A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we show that if G is a graph with maximum degree A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.展开更多
In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number...In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.展开更多
A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each e...A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E（G）, the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let X（G ） denote the smallest value k in such a ＇ G coloring of G. This parameter makes sense for graphs containing no isolated edges （we call such graphs normal）. The maximum average degree mad（G） of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad（G） 〈 5 then x＇（G） ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.展开更多
Let Ф ： E（G）→ {1, 2,…, k}be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if ∑eЭu Ф（e）≠∑eЭu Ф（e） for each edge uv∈E（G）.The smallest value k for ...Let Ф ： E（G）→ {1, 2,…, k}be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if ∑eЭu Ф（e）≠∑eЭu Ф（e） for each edge uv∈E（G）.The smallest value k for which G has such a coloring is denoted by χ＇Σ（G） which makes sense for graphs containing no isolated edge（we call such graphs normal）. It was conjectured by Flandrin et al. that χ＇Σ（G） ≤△（G） ＋ 2 for all normal graphs,except for C5. Let mad（G） = max{（2｜E（H）｜）/（｜V（H）｜）｜HЭG}be the maximum average degree of G. In this paper,we prove that if G is a normal graph with△（G）≥5 and mad（G） 〈 3-2/（△（G））, then χ＇Σ（G）≤△（G） ＋ 1. This improves the previous results and the bound △（G） ＋ 1 is sharp.展开更多
基金Supported by the Natural Science Foundation of Chongqing Science and Technology Commission (Grant No.2007BB2123)
文摘A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we show that if G is a graph with maximum degree A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.
文摘In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.
基金Supported by National Natural Science Foundation of China(Grant Nos.11371355,11471193,11271006,11631014)the Foundation for Distinguished Young Scholars of Shandong Province(Grant No.JQ201501)the Fundamental Research Funds of Shandong University and Independent Innovation Foundation of Shandong University(Grant No.IFYT14012)
文摘A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E（G）, the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let X（G ） denote the smallest value k in such a ＇ G coloring of G. This parameter makes sense for graphs containing no isolated edges （we call such graphs normal）. The maximum average degree mad（G） of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad（G） 〈 5 then x＇（G） ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.
基金Supported by the National Natural Science Foundation of China(11471193,11631014)the Foundation for Distinguished Young Scholars of Shandong Province(JQ201501)+1 种基金the Fundamental Research Funds of Shandong UniversityIndependent Innovation Foundation of Shandong University(IFYT14012)
文摘Let Ф ： E（G）→ {1, 2,…, k}be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if ∑eЭu Ф（e）≠∑eЭu Ф（e） for each edge uv∈E（G）.The smallest value k for which G has such a coloring is denoted by χ＇Σ（G） which makes sense for graphs containing no isolated edge（we call such graphs normal）. It was conjectured by Flandrin et al. that χ＇Σ（G） ≤△（G） ＋ 2 for all normal graphs,except for C5. Let mad（G） = max{（2｜E（H）｜）/（｜V（H）｜）｜HЭG}be the maximum average degree of G. In this paper,we prove that if G is a normal graph with△（G）≥5 and mad（G） 〈 3-2/（△（G））, then χ＇Σ（G）≤△（G） ＋ 1. This improves the previous results and the bound △（G） ＋ 1 is sharp.
