检索结果-南通市图书馆

Chromatic number and subtrees of graphs

在线全文

学校读者我要写书评

暂无评论

Frontiers of Mathematics in China 2017年第2期12卷 441-457页

作者： baogang xu Yingli ZHANG Institute of Mathematics School of Mathematical Sciences Nanjing Normal UniversityNanjing 210023 China

Let G and H be two induced subgraph isomorphic to conjectured that, for every tree function, depending only on T graphs. We say that G induces H if G has an H. A. Gyarfas and D. Sumner, independently, T, there exists a function fT, called binding with the property that every graph G with chromatic number fT（ω（G）） induces T. A. Gyarfas, E. Szemeedi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyarfas et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with co（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（14^r-1（r - 1）!） times. We extend the approach of A. Gyarfas and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott＇s upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω（G） ≤ k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O（6^r-2） times.

关键词： Chromatic number clique number induced tree subdivision

Acyclic edge coloring of planar graphs without adjacent cycles

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China Mathematics 2014年第2期57卷 433-442页

作者： WAN Min xu baogang Institute of Mathematics School of Mathematical SciencesNanjing Normal University Department of Mathematics School of SciencesShihezi University

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in *** acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of *** G be a planar graph with maximum *** this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.

关键词： acyclic edge coloring planar graph adjacent cycles

Improved bounds on linear coloring of plane graphs

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2010年第7期53卷 1891-1898页

作者： Dong Wei xu baogang Zhang XiaoYan Nanjing Normal Univ Sch Math Sci Nanjing 210097 Peoples R China Nanjing XiaoZhuang Coll Sch Math & Informat Technol Nanjing 210017 Peoples R China

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).

关键词： girth plane graph linear coloring cycle

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2014年第12期57卷 2437-2462页

作者： xu baogang YU XingXing ZHANG XiaoYan ZHANG Zan-Bo School of Mathematical Sciences and Institute of Mathematics Nanjing Normal University School of Mathematics Georgia Institute of Technology Faculty of Electrical Engineering Mathematics and Computer Science University of Twente Department of Computer Engineering Guangdong Industry Technical College

We consider the design of semidefinite programming （SDP） based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance （MHC-LU）： Find a partition of the vertices of a weighted hypergraph H = （V, E） into two subsets V1, V2 with ｜｜V2｜ - ｜1/1 ｜｜ ≤ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance （MC-LU）, Max Set Splitting, Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/｜V｜. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko （2000） on Max Hypergraph Bisection （MHC-LU with u = 0）, and results of Andersson and Engebretsen （1999）, Gaur and Krishnamurti （2001） and Zhang et al. （2004） on Max Set Splitting （MHC-LU with u = ｜V｜）. Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli （2007） is responsible for the improvement of a result of Galbiati and Maffioli （2007） on MC-LU for some range of τ.

关键词： max hypergraph cut with limited unbalance approximation algorithm performance ratio semidefinite programming relaxation

HAJOS' CONJECTURE AND CONNECTIVITY OF EULERIAN GRAPHS

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2002年第3期15卷 295-298页

作者： xu baogang (School of Mathematics and Computer Science, Nanjing Normal University, Nanjing 210097, China) School of Mathematics and Computer Science Nanjing Normal University Nanjing 210097

Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show that to prove Hajos' conjecture, it is sufficient to prove this new conjecture for 3-connected graphs. Furthermore, a special 3-cut is considered also.

关键词： Circuit decomposition connectivity eulerian graph.

在线全文

学校读者我要写书评

暂无评论

图的划分:一些进展与未解决问题(英文)

数学进展 2016年第1期45卷 1-20页

作者：许宝刚南京师范大学数学科学学院数学研究所南京江苏210023

图的划分问题是图论研究中最重要的一个问题之一,图论研究的很多问题都是特殊形式的划分问题,比如经典染色理论要求将图划分成最少的独立集,而最大尼-部子图问题则是要找图中边数最多的一个k-部子图.本文给出划分问题的一些最新进展,以... 详细信息

图的划分问题是图论研究中最重要的一个问题之一,图论研究的很多问题都是特殊形式的划分问题,比如经典染色理论要求将图划分成最少的独立集,而最大尼-部子图问题则是要找图中边数最多的一个k-部子图.本文给出划分问题的一些最新进展,以及一些尚未解决的问题,其中大部分是来自于求最大k-部子图的相关领域.

关键词：图划分进展问题

在线全文

学校读者我要写书评

暂无评论

奇可标号图类最优界定函数的相关研究

中国科学：数学 2020年第9期50卷 1337-1360页

作者：吴蓉许宝刚南京师范大学数学科学学院南京210023

令G表示一类图.如果存在一个函数f使得对于任意的G∈G都有χ(G)≤f(ω(G)),那么称G是χ-界图类,且称f是G的一个界定(binding)函数.本文研究奇可标号图类最优界定函数相关问题,证明一类无4-洞奇可标号图有线性界定函数.

关键词：偶洞色数团数

在线全文

学校读者我要写书评

暂无评论

超图与图公平划分的l-元组

中国科学：数学 2019年第7期49卷 1063-1074页

作者：金晶许宝刚南京师范大学数学科学学院南京210023 南京师范大学泰州学院泰州225300

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数。 Fan和Hou(2017)证明了每个最大度为△的m阶图G都存在一个k部划分(V1, V2,..., Vk),使得对于任意1≤i 详细信息

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数。 Fan和Hou(2017)证明了每个最大度为△的m阶图G都存在一个k部划分(V1, V2,..., Vk),使得对于任意1≤i

关键词：公平划分一致超图简单图

(4m, m)-CHOOSABILITY OF PLANE GRAPHS

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2001年第2期14卷 174-178页

作者： xu baogang (Institute of Systems Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China) 中科院系统科学所北京 100080

A graph G is (a, b)-choosable for nonnegative integers a > b if for any given family {A(v)\v ε V(G)} of sets A(v) of cardinality a there exists a family {B(v)\v ε V(G)} of subsets B(v) A(v) of cardinality b such that B(u) B(v) =θ whenever uv E(G). It is Proved in this paper that every plane graph in which no two triangles share a common vertex is (4m, m)-choosable for every nonnegative integer m.

关键词： Choosable plane graph triangle.