随机图的f-染色的分类Ⅱ

来源 :数学进展 | 被引量 : 0次 | 上传用户：lin_yuqi

【摘要】

：

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一对顶点以概率p被随机且独立地选择为图G的边.对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数.在这篇文章中,我们给出随机图G(n,p)是f-第一类的一个充分条件.

【作者】

：

蔡建生熊亚萍

【机构】

：

潍坊学院数学与信息科学学院,潍坊,山东,261061;山东师范大学数学与统计学院,济南,山东,250358

【出处】

：

数学进展

【发表日期】

：

2021年5期

【关键词】

：

随机图 f-染色 Lovász局部引理

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

其他文献

几何曲线流和可积系统

本文综述了不变几何曲线流和可积系统关系的相关研究.证明了包括KdV方程、修正KdV方程、非线性可积薛定谔方程和Burgers方程在内的一些古典可积系统自然来源于中心等仿射几何、欧氏几何和相似几何中的平面或空间曲线流,刻画了对应于可积系统一些特殊解的曲线流.并给出了可积系统的Miura变换、B(a)cklund变换和哈密顿结构等典型性质的几何描述.还建立了曲线流和Camassa-Holm类方程的一些对应关系.“,”This paper is a survey on the relationship betw

期刊

geometric curve flowintegrable systembi-Hamiltonian structuresolitonMiura tr

基于布尔矩阵的Scott拓扑子基

Scott拓扑是domain理论的基础之一,是domain结构的核心部分.本文首先探讨有限Scott拓扑空间的矩阵表示.由于通过基可获得Scott拓扑的结构及其性质,因此通过矩阵判断开集族为基或极小基是一个有意义的研究问题.于是,在该矩阵框架下,进一步通过基探讨Scott拓扑空间与其子空间之间的联系.随后设计极小基和极小子基的矩阵算法.最后通过数值实验验证所提算法的有效性.“,”Scott topology is one of the foundations in domain theory,which

期刊

algorithmBoolean matrixbasesub-baseScott topology

Kite系的4-相交数问题

期刊

kite system4-way intersection(HG)-design

可积系统与正交多项式交叉研究概述

本文概述可积系统与正交多项式相关的交叉研究工作,重点介绍与正交多项式相关的Toda型方程、Camassa-Holm类型尖峰孤子系统以及相关的随机矩阵及离散的活动标架等方面的研究.

期刊

可积系统正交多项式尖峰孤子系统随机矩阵离散活动标架

不含带弦6-圈和项链图的平面图是DP-4-可染的

DP 染色是 Dvo?ák 和 Postle 在[J. Combin. Theory Ser.B,2018,129:38-54]中提出的,它是列表染色的一个推广.2018年,Kim和Ozeki证明了不含k-圈的平面图是DP-4-可染的,这里k=3,4,5,6.本文改进以上结果给出平面图是DP-4-可染的一个充分条件,证明不含带弦6-圈和项链图的平面图是DP-4-可染的.“,”DP-coloring(also known as correspondence coloring)introduced by Dv

期刊

DP-chromatic numberplanar graphcyclechord

并封闭集猜测的两个加强形式

期刊

the union-closed sets conjectureFrankl's conjecture

广义薛定谔算子的收敛速度

本文主要考虑了如下定义的广义色散方程i(6)tu+φ(√-△)u=0,(x,t)∈R×R,u(x,0)=f(x),其中φ(√-△)是带象征φ(|ξ|)的拟微分算子.当象征φ满足适当的增长条件和初值f属于Sobolev空间Hs(R)时,我们给出了广义色散方程的解点态收敛于初值的收敛速度.这个结论显著推广了最近一些文献的结果.

期刊

广义色散方程Sobolev空间收敛速度

基于有限域中的迹函数生成的大族伪随机二元格点

自从Hubert等人引入二元格点的伪随机测度以来,人们利用有限域的结构和性质构造了很多的伪随机二元格点.本文基于有限域的迹函数生成了大族n维伪随机二元格点,并研究了伪随机测度、碰撞与雪崩效应.“,”Many pseudorandom binary lattices have been given and studied by using finite fields since Hubert et al.introduced pseudorandom measures for finite pseudora

期刊

binary latticetracepseudorandom measurecollisionavalanche effect

哈密尔顿二次迭代线图的边度条件

期刊

iterated line graphsHamiltonian indexedge degree condition

图的半全约束数问题

设图G=(V,E)不含孤立点,图G的半全约束集B是E(G)的一个非空子集,满足从G中删除B后得到的无孤立点图其半全控制数大于G的半全控制数.最小半全约束集包含的边数称为半全约束数,记为bt2(G).本文证明了求一般图的半全约束数对应的判定问题是NP困难的,并且得到了树、圈、网格图Pn□P2、完全二部图以及轮图的半全约束数.

期刊

半全控制半全约束数复杂度完全二部图轮图

随机图的f-染色的分类Ⅱ

与本文相关的学术论文