A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is ...A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is the minimum number of colors needed for an injective edge coloring of G.It was conjectured that the injective chromatic index of any subcubic graph is at most 6.In this paper,we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to 6.The bound 6 is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most 6 colors for such graphs.展开更多
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.展开更多
A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a...A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.展开更多
基金Supported by the National Natural Science Foundation of China(Grant No.11771080).
文摘A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is the minimum number of colors needed for an injective edge coloring of G.It was conjectured that the injective chromatic index of any subcubic graph is at most 6.In this paper,we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to 6.The bound 6 is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most 6 colors for such graphs.
基金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.
基金partially supported by NSFC (No.12001296)Fundamental Research Funds for the Central Universities+3 种基金Nankai University (No.63201163)Shi is partially supported by NSFC (No.11922112)Natural Science Foundation of TianjinNankai Universitv (No.63206034)。
基金National Natural Science Foundation of China(No.10971025)
文摘A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.
