On the size of special class 1 graphs and (P3;k)-co-critical graphs

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)

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2021-12, Vol.344 (12), p.112604, Article 112604
Main Authors: Chen, Gang, Miao, Zhengke, Song, Zi-Xia, Zhang, Jingmei
Format: Article
Language:English
Subjects:
co-critical graphs
Edge-coloring
Ramsey-minimal
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2021.112604