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.展开更多
A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>...A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>: <em>E</em>(<em>G</em>) → {1, 2, …, <em>k</em>} such that no two adjacent edges receive the same color. A neighbor sum distinguishing <em>k</em>-edge coloring of <em>G</em> is a proper <em>k</em>-edge coloring of <em>G</em> such that <img src="Edit_28f0a24c-7d3f-4bdc-b58c-46dfa2add4b4.bmp" alt="" /> for each edge <em>uv</em> ∈ <em>E</em>(<em>G</em>). The neighbor sum distinguishing index of a graph <em>G</em> is the least integer <em>k</em> such that <em>G </em>has such a coloring, denoted by <em>χ’</em><sub>Σ</sub>(<em>G</em>). Let <img src="Edit_7525056f-b99d-4e38-b940-618d16c061e2.bmp" alt="" /> be the maximum average degree of <em>G</em>. In this paper, we prove <em>χ</em>’<sub>Σ</sub>(<em>G</em>) ≤ max{9, Δ(<em>G</em>) +1} for any normal graph <em>G</em> with <img src="Edit_e28e38d5-9b6d-46da-bfce-2aae47cc36f3.bmp" alt="" />. Our approach is based on the discharging method and Combinatorial Nullstellensatz.展开更多
基金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.
文摘A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>: <em>E</em>(<em>G</em>) → {1, 2, …, <em>k</em>} such that no two adjacent edges receive the same color. A neighbor sum distinguishing <em>k</em>-edge coloring of <em>G</em> is a proper <em>k</em>-edge coloring of <em>G</em> such that <img src="Edit_28f0a24c-7d3f-4bdc-b58c-46dfa2add4b4.bmp" alt="" /> for each edge <em>uv</em> ∈ <em>E</em>(<em>G</em>). The neighbor sum distinguishing index of a graph <em>G</em> is the least integer <em>k</em> such that <em>G </em>has such a coloring, denoted by <em>χ’</em><sub>Σ</sub>(<em>G</em>). Let <img src="Edit_7525056f-b99d-4e38-b940-618d16c061e2.bmp" alt="" /> be the maximum average degree of <em>G</em>. In this paper, we prove <em>χ</em>’<sub>Σ</sub>(<em>G</em>) ≤ max{9, Δ(<em>G</em>) +1} for any normal graph <em>G</em> with <img src="Edit_e28e38d5-9b6d-46da-bfce-2aae47cc36f3.bmp" alt="" />. Our approach is based on the discharging method and Combinatorial Nullstellensatz.
