The list extremal number f（G） is defined for a graph G as the smallest integer k such that the join of G with a stable set of size k is not ｜V（G）｜-choosable. In this paper, we find the exact value of f（G）, whe...The list extremal number f（G） is defined for a graph G as the smallest integer k such that the join of G with a stable set of size k is not ｜V（G）｜-choosable. In this paper, we find the exact value of f（G）, where G is the union of edge-disjoint cycles of length three, four, five and six. Our results confirm two conjectures posed by S. Gravier, F. Maffray and B. Mohar.展开更多
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is （A ＋ 1）-edge-choosable and...A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is （A ＋ 1）-edge-choosable and （△ ＋ 2）- total-choosable if △ ≥ 16, and is A-edge-choosable and （△ ＋ 1）-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.展开更多
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.展开更多
Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a c...Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.展开更多
A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.It is known that the list edge chromatic numberχ′l(G)of any outer-1-planar g...A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.It is known that the list edge chromatic numberχ′l(G)of any outer-1-planar graph G with maximum degreeΔ(G)≥5 is exactly its maximum degree.In this paper,we proveχ′l(G)=Δ(G)for outer-1-planar graphs G withΔ(G)=4 and with the crossing distance being at least 3.展开更多
A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set ...A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.The list 2-distance chromatic number of G denoted byχ_(2)^(l)(G)is the least integer k for which G is list 2-distance k-colorable.In this paper,we prove that every planar graph with g(G)≥5 and△(G)≥40 is list 2-distance(△(G)+4)-colorable.展开更多
LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic number...LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.展开更多
Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ r...Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.展开更多
Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distingu...Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.展开更多
A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G h...A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.展开更多
A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy...A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.展开更多
In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group （△ （G）＋1）-edge-choosable, and some planar graphs with large girth and maximum degree are group △（...In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group （△ （G）＋1）-edge-choosable, and some planar graphs with large girth and maximum degree are group △（G）-edge-choosable.展开更多
A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- cho...A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- choosable. It is clear that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. Recently, Kostochka, Stiebitz and Woodall showed that Ohba＇s conjecture holds for complete multipartite graphs with partite size at most five. But the complete multipartite graphs with no restriction on their partite size, for which Ohba＇s conjecture has been verified are nothing more than the graphs Kt＋3,2.（k-t-l）,l.t by Enotomo et al., and gt＋2,3,2.（k-t-2）,l.t for t ≤ 4 by Shen et al.. In this paper, using the concept of f-choosable （or Lo-size-choosable） of graphs, we show that Ohba＇s conjecture is also true for the graphs gt＋2,3,2.（k-t-2）,l.t when t ≥ 5. Thus, Ohba＇s conjecture is true for graphs Kt＋2,3,2,（k-t-2）,l＊t for all integers t 〉 1.展开更多
文摘The list extremal number f（G） is defined for a graph G as the smallest integer k such that the join of G with a stable set of size k is not ｜V（G）｜-choosable. In this paper, we find the exact value of f（G）, where G is the union of edge-disjoint cycles of length three, four, five and six. Our results confirm two conjectures posed by S. Gravier, F. Maffray and B. Mohar.
文摘A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is （A ＋ 1）-edge-choosable and （△ ＋ 2）- total-choosable if △ ≥ 16, and is A-edge-choosable and （△ ＋ 1）-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.
基金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.
文摘Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.
基金supported by the National Natural Science Foundation of China (Nos. 11871055,11301410)the Youth Talent Support Plan of Xi’an Association for Science and Technology,China (2018-6)
文摘A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.It is known that the list edge chromatic numberχ′l(G)of any outer-1-planar graph G with maximum degreeΔ(G)≥5 is exactly its maximum degree.In this paper,we proveχ′l(G)=Δ(G)for outer-1-planar graphs G withΔ(G)=4 and with the crossing distance being at least 3.
基金supported by the National Natural Science Foundation of China(Nos.11771443,12071265)。
文摘A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.The list 2-distance chromatic number of G denoted byχ_(2)^(l)(G)is the least integer k for which G is list 2-distance k-colorable.In this paper,we prove that every planar graph with g(G)≥5 and△(G)≥40 is list 2-distance(△(G)+4)-colorable.
基金Supported by National Natural Science Foundation of China(Grant Nos.11201440 and 11271006)Graduate Independent Innovation Foundation of Shandong University(Grant No.yzc12100)
文摘LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.
文摘Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.
基金supported by National Natural Science Foundation of China(Grant Nos.11101243 and 11371355)the Research Fund for the Doctoral Program of Higher Education of China(Grant No.20100131120017)the Scientific Research Foundation for the Excellent Middle Aged and Youth Scientists of Shandong Province of China(Grant No.BS2012SF016)
文摘Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.
基金supported by National Natural Science Foundation of China(Grant No.11901318)the Fundamental Research Funds for the Central Universities,Nankai University(Grant No.63191425)supported by National Natural Science Foundation of China(Grant Nos.11571149 and 11971205)
文摘A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.
基金the Science Foundation of the Education Department of Hebei Province (2005108).
文摘A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.
基金Supported by the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2013JQ1002)the Fundamental Research Funds for the Central Universities(Grant No.K5051370003)National Natural Science Foundation of China(Grant Nos.11101243,11201440,11301410 and 61070230)
文摘In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group （△ （G）＋1）-edge-choosable, and some planar graphs with large girth and maximum degree are group △（G）-edge-choosable.
基金Supported by the National Natural Science Foundation of China(No.10871058)the project for mathematical research from the Natural Science Foundation of Hebei Province,China(No.08M004)Hebei Normal University of Science and Technology,China(ZDJS2009 and CXTD2012)
文摘A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- choosable. It is clear that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. Recently, Kostochka, Stiebitz and Woodall showed that Ohba＇s conjecture holds for complete multipartite graphs with partite size at most five. But the complete multipartite graphs with no restriction on their partite size, for which Ohba＇s conjecture has been verified are nothing more than the graphs Kt＋3,2.（k-t-l）,l.t by Enotomo et al., and gt＋2,3,2.（k-t-2）,l.t for t ≤ 4 by Shen et al.. In this paper, using the concept of f-choosable （or Lo-size-choosable） of graphs, we show that Ohba＇s conjecture is also true for the graphs gt＋2,3,2.（k-t-2）,l.t when t ≥ 5. Thus, Ohba＇s conjecture is true for graphs Kt＋2,3,2,（k-t-2）,l＊t for all integers t 〉 1.
