Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871138 | Discrete Applied Mathematics | 2018 | 7 Pages |
Abstract
Deciding if the edges of a graph with n vertices and maximum degree Î can be coloured with Î colours is an NP-complete problem, but a conjecture proposed by Hilton and Chetwynd in 1984, along with a result of Niessen of 2001, suggests the existence of a linear-time algorithm for the problem when restricted to graphs with Î⩾n/2. Join graphs satisfy this restriction, but no polynomial-time algorithm for determining the chromatic index of a join graph is known. This paper presents some sufficient conditions for join graphs to have chromatic index equal to Î and other results on the chromatic index of graphs with Î⩾n/2, proving that they all can be coloured with Î colours when triangle-free.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
A. Zorzi, L.M. Zatesko,