Colouring the Petals of a Graph

  • David Cariolaro
  • Gianfranco Cariolaro

Abstract

A petal graph is a connected graph $G$ with maximum degree three, minimum degree two, and such that the set of vertices of degree three induces a $2$–regular graph and the set of vertices of degree two induces an empty graph. We prove here that, with the single exception of the graph obtained from the Petersen graph by deleting one vertex, all petal graphs are Class $1$. This settles a particular case of a conjecture of Hilton and Zhao.

Published
2003-01-29
Article Number
R6