The edge-chromatic class of regular graphs of degree 4 and their complements

DOI10.1016/0166-218X(87)90069-2MaRDI QIDQ1087882zbMATH OpenDBLPWikidataFDO

Authors Amanda G. Chetwynd, A. J. W. Hilton

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(87)90069-2

zbMATH Keywords

1-factorizationedge-colouringregular graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

When scheduling round robin tournaments, how many rounds may be selected at random so as to be able still to complete the total schedule? In this paper it is shown that 4 rounds may always be drawn, except for one special case with 6 players. The problem is treated as the existence of a 1-factorization for the complement of a regular graph of even order, in other words that there exists an edge-colouring with no more colours than the degree of the (regular) graph, i.e. the graph is of class 1. As part of the proof a list is obtained of all 8 regular graphs of order at most 10 which are not of class 1.

Recommendations

• scientific article; zbMATH DE number 3893226
• scientific article; zbMATH DE number 3873358
• scientific article; zbMATH DE number 4156488
• The tournament scheduling problem with absences
• Regular colorings in regular graphs

Cites work

• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• On Hamilton's ideals
• Premature sets of 1-factors or how not to schedule round robin tournaments
• Regular Graphs of High Degree are 1-Factorizable
• Some Theorems on Abstract Graphs

Cited in

(8)

• An application of Tutte's theorem to 1-factorization of regular graphs of high degree
• Two conjectures on edge-colouring
• The chromatic index of a graph whose core has maximum degree two
• On 4-chromatic edge-critical regular graphs of high connectivity
• Unextendible product bases and 1-factorization of complete graphs
• scientific article; zbMATH DE number 6383856 (Why is no real title available?)
• The edge C₄graph of some graph classes
• The tournament scheduling problem with absences

This page was built for publication: The edge-chromatic class of regular graphs of degree 4 and their complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087882)