期刊文献+
共找到53篇文章
< 1 2 3 >
每页显示 20 50 100
Bondage Number of 1-Planar Graph 被引量:1
1
作者 Qiaoling Ma Sumei Zhang Jihui Wang 《Applied Mathematics》 2010年第2期101-103,共3页
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. 展开更多
关键词 DOMINATION NUMBER Bondage NUMBER 1-planar GRAPH Combinatorial PROBLEM
下载PDF
Conflict-free Incidence Coloring of Outer-1-planar Graphs
2
作者 Meng-ke QI Xin ZHANG 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2024年第4期929-942,共14页
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. 展开更多
关键词 outer-1-planar graph incidence coloring combinatorial algorithm channel assignment problem
原文传递
Acyclic Edge Coloring of 1-planar Graphs without 4-cycles
3
作者 Wei-fan Wang Yi-qiao Wang Wan-shun Yang 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2024年第1期35-44,共10页
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. 展开更多
关键词 1-planar graph acyclic edge coloring acyclic chromatic index
原文传递
List edge and list total coloring of 1-planar graphs 被引量:6
4
作者 Xin ZHANG Jianliang WU Guizhen LIU 《Frontiers of Mathematics in China》 SCIE CSCD 2012年第5期1005-1018,共14页
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. 展开更多
关键词 1-planar graph list coloring conjecture DISCHARGING
原文传递
An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs 被引量:3
5
作者 Juan LIU Yi Qiao WANG +2 位作者 Ping WANG Lu ZHANG Wei Fan WANG 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2021年第2期262-278,共17页
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. 展开更多
关键词 1-planar graph linear 2-arboricity edge-partition maximum degree
原文传递
Light Subgraphs in the Family of 1-Planar Graphs with High Minimum Degree 被引量:2
6
作者 Xin ZHANG Gui Zhen LIU Jian Liang WU 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2012年第6期1155-1168,共14页
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. 展开更多
关键词 1-planar graph LIGHTNESS HEIGHT DISCHARGING
原文传递
Acyclic Edge Coloring of Triangle-free 1-planar Graphs 被引量:2
7
作者 Wen Yao SONG Lian Ying MIAO 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2015年第10期1563-1570,共8页
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. 展开更多
关键词 Acyclic chromatic index acyclic edge coloring 1-planar graph
原文传递
Equitable Coloring of Three Classes of 1-planar Graphs 被引量:2
8
作者 Xin ZHANG Hui-juan WANG Lan XU 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2018年第2期362-372,共11页
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. 展开更多
关键词 1-planar graph equitable coloring independent crossing
原文传递
A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five 被引量:1
9
作者 Lin SUN Jian Liang WU Hua CAI 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2016年第11期1337-1349,共13页
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. 展开更多
关键词 1-planar graph total coloring discharging method GIRTH
原文传递
Linear Arboricity of Outer-1-Planar Graphs 被引量:1
10
作者 Xin Zhang Bi Li 《Journal of the Operations Research Society of China》 EI CSCD 2021年第1期181-193,共13页
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. 展开更多
关键词 Outer-1-planar graph CROSSING Linear arboricity Polynomial-time algorithm
原文传递
On Total Colorings of Some Special 1-planar Graphs
11
作者 Lin SUN Jian-liang WU Hua CAI 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2017年第3期607-618,共12页
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. 展开更多
关键词 1-planar graph total coloring discharging method GIRTH r-minimal graph
原文传递
1-planar Graphs without 4-cycles or 5-cycles are 5-colorable
12
作者 Li-li SONG Lei SUN 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2022年第1期169-177,共9页
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. 展开更多
关键词 1-planar colorable DISCHARGING VERTICES FACES
原文传递
List Edge Coloring of Outer-1-planar Graphs
13
作者 Xin ZHANG 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2020年第3期737-752,共16页
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. 展开更多
关键词 outerplanar graph outer-1-planar graph crossing distance list edge coloring
原文传递
Joins of 1-Planar Graphs
14
作者 Július CZAP Dvid HUDK Tom MADARAS 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2014年第11期1867-1876,共10页
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. 展开更多
关键词 1-planar graph join product
原文传递
1-平面图的奇着色数最多是21
15
作者 郭春强 吴宝音都仍 《新疆大学学报(自然科学版)(中英文)》 CAS 2023年第3期267-273,共7页
对于任何一个图G的正常点着色φ而言,如果对于任何一个非孤立点x,存在一个颜色c使得|φ^(-1)(c)∩N_(G)(x)|是奇的,则φ被称为图G的奇着色.如果一个图能画在一个平面上,使得每一边至多被另一条边相交,则这样的图被称为1-平面图.证明了... 对于任何一个图G的正常点着色φ而言,如果对于任何一个非孤立点x,存在一个颜色c使得|φ^(-1)(c)∩N_(G)(x)|是奇的,则φ被称为图G的奇着色.如果一个图能画在一个平面上,使得每一边至多被另一条边相交,则这样的图被称为1-平面图.证明了任何一个1-平面图是奇21-着色的,改进了最近由Cranston,Lafferty和Song得到的界23. 展开更多
关键词 正常着色 奇着色 1-平面图
下载PDF
1-平面图的线性荫度(英文) 被引量:8
16
作者 张欣 刘桂真 吴建良 《运筹学学报》 CSCD 2011年第3期38-44,共7页
证明了最大度△≥33的1-平面图的线性荫度为[△/2]
关键词 1-平面图 1-嵌入图 线性荫度
下载PDF
不含相邻4-圈的1-平面图边染色 被引量:1
17
作者 宋文耀 苗连英 张佳丽 《湖北大学学报(自然科学版)》 CAS 2013年第2期209-213,共5页
利用权转移方法证明最大度为9且不含相邻4-圈的1-平面图是9-边可染的.
关键词 1-平面图 边染色 权转移
下载PDF
激光二极管泵浦1319nm单频可调谐激光器技术研究 被引量:7
18
作者 赵严 高春清 +5 位作者 王青 杨苏辉 曹一磊 李家泽 魏光辉 洪冬梅 《北京理工大学学报》 EI CAS CSCD 北大核心 2003年第4期484-487,共4页
采用激光二极管泵浦单块非平面环形腔Nd:YAG激光器,获得了1319nm的单频可调谐激光输出,输出功率为99mW,斜效率为29%.用扫描F-P法和狭缝扫描法分别测量了激光器的纵模、横模特性,激光器为单纵模、基横模运转.用温度调谐方法研究了激光器... 采用激光二极管泵浦单块非平面环形腔Nd:YAG激光器,获得了1319nm的单频可调谐激光输出,输出功率为99mW,斜效率为29%.用扫描F-P法和狭缝扫描法分别测量了激光器的纵模、横模特性,激光器为单纵模、基横模运转.用温度调谐方法研究了激光器的频率调谐特性,结果是调谐范围为14GHz,连续温度调谐系数为2.1GHz/℃. 展开更多
关键词 非平面环形腔 1319nm单频激光器 频率调谐
下载PDF
不含3-圈的1-平面图的列表边染色与列表全染色(英文)
19
作者 宋文耀 苗连英 张淑洁 《华东师范大学学报(自然科学版)》 CAS CSCD 北大核心 2014年第3期40-44,共5页
一个图称为是1-平面的,当且仅当它可以画在一个平面上,使其任何一条边最多交叉另外一条边.本文证明了最大度△≥15且不含三角形的1-平面图G是△-边可选择的和(△+1)-全可选择的.
关键词 1-平面图 差值转移方法 最大度 可选择性
下载PDF
1-平面图及其子类的染色 被引量:3
20
作者 张欣 刘维婵 《运筹学学报》 CSCD 北大核心 2017年第4期135-152,共18页
如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶... 如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果. 展开更多
关键词 1-平面图 NIC-平面图 IC-平面图 1-平面图 染色
下载PDF
上一页 1 2 3 下一页 到第
使用帮助 返回顶部