On the size of special class 1 graphs and (P3;k)-co-critical graphs |
| |
Affiliation: | 1. School of Mathematics and Statistics, Ningxia University, Yinchuan, Ningxia 750021, China;2. Research Institute of Mathematical Science and Department of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, Jiangsu 221116, China;3. Department of Mathematics, University of Central Florida, Orlando, FL 32816, USA;4. The High School affiliated to the Southern University of Science and Technology, Shenzhen, Guangdong 518133, China |
| |
Abstract: | A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index of G is Δ or . A graph G is class 1 if , and class 2 if ; G is Δ-critical if it is connected, class 2 and for every . A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, for every . Such graphs have intimate relation to -co-critical graphs, where a non-complete graph G is -co-critical if there exists a k-coloring of such that G does not contain a monochromatic copy of but every k-coloring of contains a monochromatic copy of for every . We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all -co-critical graphs. We prove that if G is a -co-critical graph on vertices, then where ε is the remainder of when divided by 2. This bound is best possible for all and . |
| |
Keywords: | co-critical graphs Ramsey-minimal Edge-coloring |
本文献已被 ScienceDirect 等数据库收录! |
|