On the chromatic index of path decompositions
type: Item
instance of: scholarly article
title: On the chromatic index of path decompositions
zbMATH Open document ID: 1049.05032
author: Peter Danziger
author: Eric Mendelsohn
author: Gaetano Quattrocchi
published in: Discrete Mathematics
publication date: 2004-08-20T00:00:00Z
review text: Given a decomposition \(D\) of a graph \(H\) into edge-disjoint copies of a graph \(G\), the chromatic index of \(D\) is the minimum number of colours in any colouring of the copies of \(G\) in \(D\) in which no two copies of \(G\) having a vertex in common get the same colour. For given \(H\) and \(G\), the minimum chromatic index problem asks for the smallest chromatic index over all decompositions \(D\) of \(H\) into copies of \(G\). The authors solve this problem for the cases when \(H\) is the complete graph on \(n\) vertices, and \(G\) is the path with two and three edges, respectively.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 2093772
zbMATH Keywords: Graph colourings
zbMATH Keywords: Graph decompositions
zbMATH Keywords: Chromatic index
zbMATH Keywords: Path designs
zbMATH Keywords: Graph designs
reviewed by: Alexander Rosa
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.027
OpenAlex ID: W2073783222
cites work: Existence of resolvable path designs
cites work: Graph properties and hypergraph colourings
cites work: Hanani triple systems
cites work: Q4873725
cites work: Class-uniformly resolvable designs
cites work: On the edge-coloring property for Hanani triple systems
cites work: Q4043098
cites work: Graph decompositions, handcuffed prisoners and balanced p-designs
cites work: Resolvable path designs
cites work: Handcuffed designs
cites work: Q4769076
cites work: Q4026150
cites work: Q3870933
cites work: Almost resolvable Pk‐decompositions of complete graphs
cites work: On path factorizations of complete multipartite graphs
cites work: On Mutually Orthogonal Resolutions and Near-Resolutions
DOI: 10.1016/J.DISC.2003.11.027
Recommended article: Q4294602
Recommended article: The chromatic index of complete multipartite graphs
Recommended article: Q4528768
Recommended article: On the chromatic spectrum of acyclic decompositions of graphs
Recommended article: Q4735206
Recommended article: On the chromatic index of almost all graphs
Recommended article: The chromatic distinguishing index of certain graphs
Recommended article: Path chromatic numbers of graphs
Recommended article: Chromaticity of the complements of paths and cycles
description: scientific article; zbMATH DE number 2093772