The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that ...The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.展开更多
A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum...A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum number of pages in which it can be embedded.Determining the pagenumber of a graph is NP-hard.A graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once.The anthors prove that the pagenumber of 1-planar graphs is at most 10.展开更多
Given a simple graph G=(V,E)and its(proper)total coloringϕwith elements of the set{1,2,⋯,k},let wϕ(v)denote the sum of the color of v and the colors of all edges incident with v.If for each edge uv∈E,wϕ(u)≠wϕ(v),we ...Given a simple graph G=(V,E)and its(proper)total coloringϕwith elements of the set{1,2,⋯,k},let wϕ(v)denote the sum of the color of v and the colors of all edges incident with v.If for each edge uv∈E,wϕ(u)≠wϕ(v),we callϕa neighbor sum distinguishing total coloring of G.Let L={Lx∣x∈V⋃E}be a set of lists of real numbers,each of size k.The neighbor sum distinguishing total choosability of G is the smallest k for which for any specified collection of such lists,there exists a neighbor sum distinguishing total coloring using colors from Lx for each x∈V⋃E,and we denote it by[Math Processing Error].The known results of neighbor sum distinguishing total choosability are mainly about planar graphs.In this paper,we focus on 1-planar graphs.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.We prove that[Math Processing Error]for any 1-planar graph G withΔ≥15,whereΔis the maximum degree of G.展开更多
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 graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph...A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.展开更多
The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests,whose component trees are paths of length at most 2.In this paper,we prove that if G is a ...The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests,whose component trees are paths of length at most 2.In this paper,we prove that if G is a 1-planar graph with maximum degree Δ,then la_(2)(G)≤[(Δ+1)/2]+7.This improves a known result of Liu et al.(2019) that every 1-planar graph G has la_(2)(G)≤[(Δ+1)/2]+14.We also observe that there exists a 7-regular 1-planar graph G such that la2(G)=6=[(Δ+1)/2]+2,which implies that our solution is within 6 from optimal.展开更多
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V （K1 ∪ K2...A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V （K1 ∪ K2） with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V （K1∪K2） with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.展开更多
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. A gra...A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. 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 X＇a（G） ≤△ A（G）＋ 22, if G is a triangle-free 1-planar graph.展开更多
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, we verify the total coloring conjecture for every 1-planar graph G if either △（G） ≥9 and g...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, we verify the total coloring conjecture for every 1-planar graph G if either △（G） ≥9 and g（G）≥ 4, or △（G） ≥ 7 and g（G）≥5, where △（G） is the maximum degree of G and g（G） is the girth of G.展开更多
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, we prove that every 1-planar graph G with maximum degree △（G） 〉 12 and girth at least five...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, we prove that every 1-planar graph G with maximum degree △（G） 〉 12 and girth at least five is totally （△（G）＋1）-colorable.展开更多
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.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Mat...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.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=3.It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.展开更多
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.展开更多
An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get disti...An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.展开更多
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring u...An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.展开更多
A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once.In this paper,we study 1-planar graph joins.We prove that the join G ＋ H is 1-planar if and only if the pair ...A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once.In this paper,we study 1-planar graph joins.We prove that the join G ＋ H is 1-planar if and only if the pair [G,H] is subgraph-majorized by one of pairs [C3 ∪ C3,C3],[C4,C4],[C4,C3],[K2,1,1,P3] in the case when both elements of the graph join have at least three vertices.If one element has at most two vertices,then we give several necessary/sufficient conditions for the bigger element.展开更多
We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices...We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.展开更多
A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge.A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such ...A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge.A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color.A graph that can be assigned a proper k-coloring is k-colorable.A cycle is a path of edges and vertices wherein a vertex is reachable from itself.A cycle contains k vertices and k edges is a k-cycle.In this paper,it is proved that 1-planar graphs without 4-cycles or 5-cycles are 5-colorable.展开更多
An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference betw...An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.展开更多
Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))...A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.展开更多
文摘The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.
基金supported by the National Natural Science Foundation of China(Nos.12371356,12401462)the Natural Science Foundation of Shanxi Province(No.20210302123097).
文摘A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum number of pages in which it can be embedded.Determining the pagenumber of a graph is NP-hard.A graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once.The anthors prove that the pagenumber of 1-planar graphs is at most 10.
基金supported by Guangdong Basic and Applied Basic Research Foundation(Natural Science Foundation of Guangdong Province,China,Grant No.2025A1515011904)the National Natural Science Foundation of China(Nos.12101285,12171222)+4 种基金the Natural Science Foundation of Xinjiang Uygur Autonomous Region(2016D01C006)Guangdong Philosophy and Social Sciences Planning Project(Grant No.GD22CXW01)Research Platforms and Projects of Colleges and Universities in Guangdong(Grant No.2022KTSCX071)Scientific Research Innovation Project of Lingnan Normal University(LT2401)Lingnan Normal University(No.LT2410).
文摘Given a simple graph G=(V,E)and its(proper)total coloringϕwith elements of the set{1,2,⋯,k},let wϕ(v)denote the sum of the color of v and the colors of all edges incident with v.If for each edge uv∈E,wϕ(u)≠wϕ(v),we callϕa neighbor sum distinguishing total coloring of G.Let L={Lx∣x∈V⋃E}be a set of lists of real numbers,each of size k.The neighbor sum distinguishing total choosability of G is the smallest k for which for any specified collection of such lists,there exists a neighbor sum distinguishing total coloring using colors from Lx for each x∈V⋃E,and we denote it by[Math Processing Error].The known results of neighbor sum distinguishing total choosability are mainly about planar graphs.In this paper,we focus on 1-planar graphs.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.We prove that[Math Processing Error]for any 1-planar graph G withΔ≥15,whereΔis the maximum degree of G.
文摘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 Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010)the Fundamental Research Funds for the Central Universities(No.JB170706)+5 种基金the Specialized Research Fund for the Doctoral Program of Higher Education(No.20130203120021)the National Natural Science Foundation of China(No.11301410)the National Natural Science Foundation of China(No.11501316)the Shandong Provincial Natural Science Foundation,China(No.ZR2014AQ001)the China Postdoctoral Science Foundation(No.2015M570569)supported by the Natural Science Foundation of Xinjiang Province of China(No.2015211A003)
文摘A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.
文摘The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests,whose component trees are paths of length at most 2.In this paper,we prove that if G is a 1-planar graph with maximum degree Δ,then la_(2)(G)≤[(Δ+1)/2]+7.This improves a known result of Liu et al.(2019) that every 1-planar graph G has la_(2)(G)≤[(Δ+1)/2]+14.We also observe that there exists a 7-regular 1-planar graph G such that la2(G)=6=[(Δ+1)/2]+2,which implies that our solution is within 6 from optimal.
基金Supported by National Natural Science Foundation of China (Grant Nos. 10971121, 11026184, 61070230)Research Fund for the Doctoral Program of Higher Education (Grant No. 20100131120017)+1 种基金Graduate Independent Innovation Foundation of Shandong University (Grant No. yzc10040)the financial support from the Chinese Ministry of Education Prize for Academic Doctoral Fellows
文摘A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V （K1 ∪ K2） with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V （K1∪K2） with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.
基金Supported by National Natural Science Foundation of China(Grant No.11271365)
文摘A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. 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 X＇a（G） ≤△ A（G）＋ 22, if G is a triangle-free 1-planar graph.
基金Supported by the scientific research program of Xinjiang Uygur Autonomous Region grant 2016D01C012 the Scientific Research Program(XJEDU2016I046)of the Higher Education Institution of Xinjiang
文摘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, we verify the total coloring conjecture for every 1-planar graph G if either △（G） ≥9 and g（G）≥ 4, or △（G） ≥ 7 and g（G）≥5, where △（G） is the maximum degree of G and g（G） is the girth of G.
基金supported by National Natural Science Foundation of China(Grant No.11271006)
文摘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, we prove that every 1-planar graph G with maximum degree △（G） 〉 12 and girth at least five is totally （△（G）＋1）-colorable.
基金supported by the Fundamental Research Funds for the Central Universities(No.JB170706)the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010)+2 种基金the National Natural Science Foundation of China(Nos.11871055 and 11301410)supported by the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JQ1031)the National Natural Science Foundation of China(Nos.11701440 and 11626181).
文摘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.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=3.It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.
基金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 Research Funds for the Central Universities(No.QTZX22053)the National Natural Science Foundation of China(No.11871055)。
文摘An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.
基金Research supported by the National Natural Science Foundation of China (No.12031018)Research supported by the National Natural Science Foundation of China (No.12071048)+3 种基金Research supported by the National Natural Science Foundation of China(No.12071351)Science and Technology Commission of Shanghai Municipality (No.18dz2271000)Doctoral Scientific Research Foundation of Weifang University (No.2021BS01)Natural Science Foundation of Shandong Province (No.ZR2022MA060)。
文摘An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.
基金Supported by the Agency of Slovak Ministry of Education for the Structural Funds of the EU under project ITMS:26220120007by Science and Technology Assistance Agency under the contract No.APVV-0023-10by Slovak VEGA grant No.1/0652/12
文摘A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once.In this paper,we study 1-planar graph joins.We prove that the join G ＋ H is 1-planar if and only if the pair [G,H] is subgraph-majorized by one of pairs [C3 ∪ C3,C3],[C4,C4],[C4,C3],[K2,1,1,P3] in the case when both elements of the graph join have at least three vertices.If one element has at most two vertices,then we give several necessary/sufficient conditions for the bigger element.
文摘We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.
基金supported by the National Natural Science Foundation of China(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2019MA032)。
文摘A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge.A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color.A graph that can be assigned a proper k-coloring is k-colorable.A cycle is a path of edges and vertices wherein a vertex is reachable from itself.A cycle contains k vertices and k edges is a k-cycle.In this paper,it is proved that 1-planar graphs without 4-cycles or 5-cycles are 5-colorable.
文摘An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
基金Supported by the National Natural Science Foundation of China(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2019MA032)。
文摘A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.
