A coloring of a graph G is injective if its restriction to the neighbour of any vertex is injective.The injective chromatic number x_(i)(G)of a graph G is the least k such that there is an injective k-coloring.In this...A coloring of a graph G is injective if its restriction to the neighbour of any vertex is injective.The injective chromatic number x_(i)(G)of a graph G is the least k such that there is an injective k-coloring.In this paper,we prove that for each planar graph with g≥5 and Δ(G)≥20,xi(G)≤Δ(G)+3.展开更多
A k-coloring of a graph G is a mapping c:V(G)→{1,2,···,k}.The coloring c is called injective if any two vertices have a common neighbor get distinct colors.A graph G is injectively k-choosable if for a...A k-coloring of a graph G is a mapping c:V(G)→{1,2,···,k}.The coloring c is called injective if any two vertices have a common neighbor get distinct colors.A graph G is injectively k-choosable if for any color list L of admissible colors on V(G)of size k allows an injective coloringφsuch thatφ(v)∈L(v)for each v∈V(G).Letχ;(G),χ;(G)denote the injective chromatic number and injective choosability number of G,respectively.In this paper,we show thatχ;(G)≤△+4 if△≥22 andχ;(G)≤△+5 if△≥15,where G is a triangle-free planar graph and without intersecting 4-cycles.展开更多
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 coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective ch...A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.展开更多
Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtaine...Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.展开更多
基金the National Natural Science Foundation of China(No.11771403).
文摘A coloring of a graph G is injective if its restriction to the neighbour of any vertex is injective.The injective chromatic number x_(i)(G)of a graph G is the least k such that there is an injective k-coloring.In this paper,we prove that for each planar graph with g≥5 and Δ(G)≥20,xi(G)≤Δ(G)+3.
基金supported by the National Natural Science Foundation of China(Nos.12071351,11571258)。
文摘A k-coloring of a graph G is a mapping c:V(G)→{1,2,···,k}.The coloring c is called injective if any two vertices have a common neighbor get distinct colors.A graph G is injectively k-choosable if for any color list L of admissible colors on V(G)of size k allows an injective coloringφsuch thatφ(v)∈L(v)for each v∈V(G).Letχ;(G),χ;(G)denote the injective chromatic number and injective choosability number of G,respectively.In this paper,we show thatχ;(G)≤△+4 if△≥22 andχ;(G)≤△+5 if△≥15,where G is a triangle-free planar graph and without intersecting 4-cycles.
基金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 the National Natural Science Foundation of China (No.11871377)。
文摘A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.
基金This research was supported by the National Natural Science Foundation of China(Nos.11571180 and 11331003)the Natural Science Foundation of Jiangsu Higher Education Institutions of China(No.17KJB110010).
文摘Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.
