检索结果-南通市图书馆

Acyclic Edge Coloring of 1-planar graphs without 4-cycles

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2024年第1期40卷 35-44页

作者： Wei-fan Wang Yi-qiao Wang Wan-shun Yang Department of Mathematics Zhejiang Normal UniversityJinhua321004China School of Management Beijing University of Chinese MedicineBeijing100029China School of Mathematics and Information Science Weifang UniversityWeifang261061China

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

An Improved Upper Bound on the Linear 2-arboricity of 1-planar graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2021年第2期37卷 262-278页

作者： Juan LIU Yi Qiao WANG Ping WANG Lu ZHANG Wei Fan WANG Department of Mathematics Zhejiang Normal UniversityJinhua 321004P.R.China School of Management Beijing University of Chinese MedicineBeijing 100029P.R.China Department of Mathematics and Statistics St.Francis Xavier UniversityAntigonishNova ScotiaCanada

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

Equitable Coloring of Three Classes of 1-planar graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2018年第2期34卷 362-372页

作者： Xin ZHANG Hui-juan WANG Lan XU School of Mathematics and Statistics Xidian University Xi'an 710071 China College of Mathematics Qingdao University Qingdao 266071 China Department of Mathematics Changji University Changji 831100 China

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

On Total Colorings of Some Special 1-planar graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2017年第3期33卷 607-618页

作者： Lin SUN Jian-liang WU Hua CAI Department of Mathematics Changji University School of Mathematics Shandong University

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

Acyclic Edge Coloring of Triangle-free 1-planar graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2015年第10期31卷 1563-1570页

作者： Wen Yao SONG Lian Ying MIAO Institute of Mathematics China University of Mining and TechnologyXuzhou

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

Joins of 1-planar graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2014年第11期30卷 1867-1876页

作者： Július CZAP Dvid HUDK Tom MADARAS Department of Applied Mathematics and Business Informatics Faculty of Economics Technical University of KoiceNěmcovej 32040 01 KoiceSlovakia VSL Software a.s.Lomen 8040 01 KoiceSlovakia Institute of Mathematics Faculty of SciencePavol Jozef afrik University Jesenn 5040 01 KoiceSlovakia

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

On Edge Colorings of 1-Toroidal graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2013年第7期29卷 1421-1428页

作者： Xin ZHANG Gui Zhen LIU Department of Mathematics Xidian University School of Mathematics Shandong University

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree △ ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree △ for each A ≤ 8.

关键词： 1-Toroidal graph 1-planar graph edge coloring

Drawing Complete Multipartite graphs on the Plane with Restrictions on Crossings

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2014年第12期30卷 2045-2053页

作者： Xin ZHANG School of Mathematics and Statistics Xidian University

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 （say NIC-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. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.

关键词： 1-planar graph independent crossings crossing number

Light Subgraphs in the Family of 1-planar graphs with High Minimum Degree

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2012年第6期28卷 1155-1168页

作者： Xin ZHANG Gui Zhen LIU Jian Liang WU School of Mathematics Shandong University

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