Article ID Journal Published Year Pages File Type
436672 Theoretical Computer Science 2014 4 Pages PDF
Abstract

A graph G is of class 1 if its edges can be colored with k colors in such a way that adjacent edges receive different colors, where k is the maximum degree of G. It is proved here that every planar graph is of class 1 if its maximum degree is at least 6 and any 5-cycle contains at most one chord.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,