An upper bound for the chromatic number of a graph and its application to timetabling problems

Clicks: 1
ID: 305879
1967
Free PDF
Article Quality & Performance Metrics
Overall Quality
Not rated
Combines reader engagement with the AI quality analysis. This article has not been analysed, so there is no overall score — reader engagement is measured and shown alongside.
AI Quality Assessment
Not analyzed
Readership in this journal

Ranked #36 of 36 articles by views in The Computer Journal

Most read Least read

Bar heights use a square-root scale.

Mint this article as an NFT
Not yet minted

Create a permanent, verifiable on-chain record of this article on the Scimatic Network. The NFT is held in your Journament account, and you can withdraw it to your own wallet at any time.

5 SUSD one-off · no wallet required
Sign in to mint
Abstract
This paper points out the connection between the basic scheduling or timetabling problem with the well known problem of colouring the vertices of a graph in such a way that (i) no two adjacent vertices are the same colour and (ii) the number of colours used is a minimum. We give an algorithm for colouring a graph subject to (i) and give a new easily determined bound for the number of colours needed. This same bound is also a new upper bound for the chromatic number of a graph in terms of the degrees of its vertices.
Reference Key
openalex_W2108301529 Use this key to autocite in the manuscript while using SciMatic Manuscript Manager or Thesis Manager
Authors Dominic Welsh
Journal The Computer Journal
Year 1967
DOI
10.1093/comjnl/10.1.85
URL
https://academic.oup.com/comjnl/article-pdf/10/1/85/1069035/100085.pdf
Keywords Keywords not found

Citations

No citations found. To add a citation, contact the admin at info@scimatic.org

Comments

No comments yet. Be the first to comment on this article.