The edge chromatic difference sequence of a cubic graph
type: Item
instance of: scholarly article
title: The edge chromatic difference sequence of a cubic graph
zbMATH Open document ID: 0894.05018
DOI: 10.1016/S0012-365X(96)00368-8
author: Michael O. Albertson
author: Ruth Haas
published in: Discrete Mathematics
publication date: 1998-09-07T00:00:00Z
review text: Let \(\gamma_r (G)\) be the maximum number of edges in an \(r\)-edge-colourable subgraph of a graph \(G\). The chromatic difference sequence \(\langle c_1,c_2,\dots, c_k\rangle\) is obtained by setting \(c_1= \gamma_1(G)\) and \(c_i= \gamma_i(G)- \gamma_{i-1} (G)\), \(i\geq 2\), where \(k\) is the chromatic index of \(G\). In the paper, the behaviour of chromatic difference sequences of cubic graphs is investigated. It is proved that \(c_1\geq c_2\geq c_4\) and \(c_1\geq c_3\geq c_4\). Examples are exhibited to show that the chromatic difference sequence of a cubic graph can, nevertheless, be non-monotonic.
reviewed by: Martin Škoviera
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1110103
zbMATH Keywords: chromatic difference sequence
zbMATH Keywords: chromatic index
zbMATH Keywords: cubic graphs
MaRDI profile type: Publication
cites work: The chromatic difference sequence of a graph
cites work: Homomorphisms of 3-chromatic graphs
cites work: Parsimonious edge coloring
cites work: Brooks' graph-coloring theorem and the independence number
cites work: Q3853641
cites work: Q5286666
cites work: Matching theory
Wikidata QID: Q126803172
description: scientific article; zbMATH DE number 1110103