南方科技大学知识苑(SUSTech KC): On the size of special class 1 graphs and (P3;k)-co-critical graphs

题名	On the size of special class 1 graphs and (P3;k)-co-critical graphs
作者	Chen，Gang 1; Miao，Zhengke 2; Song，Zi Xia 3; Zhang，Jingmei4
发表日期	2021-12-01
DOI	10.1016/j.disc.2021.112604
发表期刊	DISCRETE MATHEMATICS 影响因子和分区
ISSN	0012-365X
EISSN	1872-681X
卷号	344 期号:12
摘要	A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index χ(G) of G is Δ or Δ+1. A graph G is class 1 if χ(G)=Δ, and class 2 if χ(G)=Δ+1; G is Δ-critical if it is connected, class 2 and χ(G−e)<χ(G) for every e∈E(G). A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least (n(Δ−1)+3)/2 edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, χ(G+e)=χ(G)+1 for every e∈E(G‾). Such graphs have intimate relation to (P;k)-co-critical graphs, where a non-complete graph G is (P;k)-co-critical if there exists a k-coloring of E(G) such that G does not contain a monochromatic copy of P but every k-coloring of E(G+e) contains a monochromatic copy of P for every e∈E(G‾). We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all (P;k)-co-critical graphs. We prove that if G is a (P;k)-co-critical graph on n≥k+2 vertices, then [Formula presented] where ε is the remainder of n−⌈k/2⌉ when divided by 2. This bound is best possible for all k≥1 and n≥⌈3k/2⌉+2.
关键词	co-critical graphs Edge-coloring Ramsey-minimal
相关链接	[Scopus记录]
收录类别	SCI
语种	英语
学校署名	其他
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000712876500030
出版者	ELSEVIER
ESI学科分类	MATHEMATICS
Scopus记录号	2-s2.0-85114802321
来源库	Scopus
引用统计	被引频次[WOS]：1
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/245906
专题	南方科技大学附属教育集团_附属中学
作者单位	1.School of Mathematics and Statistics,Ningxia University,Yinchuan,750021,China 2.Research Institute of Mathematical Science,Department of Mathematics and Statistics,Jiangsu Normal University,Xuzhou,221116,China 3.Department of Mathematics,University of Central Florida,Orlando,32816,United States 4.The High School affiliated to the Southern University of Science and Technology,Shenzhen,518133,China
推荐引用方式 GB/T 7714	Chen，Gang,Miao，Zhengke,Song，Zi Xia,et al. On the size of special class 1 graphs and (P3;k)-co-critical graphs[J]. DISCRETE MATHEMATICS,2021,344(12).
APA	Chen，Gang,Miao，Zhengke,Song，Zi Xia,&Zhang，Jingmei.(2021).On the size of special class 1 graphs and (P3;k)-co-critical graphs.DISCRETE MATHEMATICS,344(12).
MLA	Chen，Gang,et al."On the size of special class 1 graphs and (P3;k)-co-critical graphs".DISCRETE MATHEMATICS 344.12(2021).