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 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 (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.
