Regular graphs and edge chromatic number
type: Item
instance of: scholarly article
title: Regular graphs and edge chromatic number
zbMATH Open document ID: 0535.05027
DOI: 10.1016/0012-365X(84)90182-1
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: For a simple graph \textit{G. Vizing}'s Theorem [On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3, 25-30 (1964)] implies that \(\Delta(G)\leq \chi(G)\leq \Delta(G)+1,\) where \(\Delta\) (G) is the maximum degree of a vertex in G and \(\chi\) (G) is the edge chromatic number of G. It is, of course, possible to add edges to G without changing its edge chromatic number. In fact, any graph G is a spanning subgraph of an edge maximal graph \(G^*\) such that \(\chi(G^*)=\chi(G)\). The question addressed here is when there exists such a graph \(G^*\) which is \(\chi\) (G)-regular. Theorem. If \(n\geq 2(k^ 2-k+1),\) n is even, \(k\geq 2\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \((k+1)\)-regular graph \(G^*\) with \(\chi(G^*)=k+1.\)- Conjecture. If \(n\geq 2k\), n is even, \(k\geq 2\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \((k+1)\)-regular graph \(G^*\) with \(\chi(G^*)=k+1\) except when \(G=K_{k,k}\) and k is odd.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3849255
zbMATH Keywords: maximum degree
zbMATH Keywords: edge chromatic number
zbMATH Keywords: spanning subgraph
author: Ralph Faudree
author: J. Sheehan
reviewed by: Linda Lesniak
MaRDI profile type: Publication
cites work: Q4187840
cites work: Some Theorems on Abstract Graphs
cites work: Q3853641
cites work: The Factorization of Linear Graphs
description: scientific article; zbMATH DE number 3849255