Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Colouring the petals of a graph | Colouring the petals of a graph David Cariolaro Department of Mathematics University of Reading RG6 6AX . davidcariolaro@ Gianfranco Cariolaro Dipartimento di Ingegneria dell Informazione Università di Padova 35133 Padova Italia cariolar@ written in memory of Prof. C. St. J. A. Nash-Williams Submitted Feb 1 2002 Accepted Jan 15 2003 Published Jan 29 2003 Mathematical Subject Classification 05C15 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. corresponding author. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R6 1 1 Introduction All graphs considered in this paper are finite undirected and without loops or multiple edges. If G is a graph we let V G and E G denote respectively the vertex and the edge set of G. If S is a set of vertices or edges of G we let G S denote the graph induced by S in G. A G and Ổ G denote the maximum and minimum degree of G respectively. The core of G denoted by Ga is the subgraph of G induced by the vertices of degree A G . If H is a subgraph of G we let r H denote the set of vertices of G which are adjacent in G to at least one vertex of H. For standard graph theoretic terminology not explicitly defined here we follow 1 . A petal graph is a connected graph G such that 1. A G 3 0 G 2 2. Ga is 2-regular 3. Every edge of G is incident with at least one vertex in Ga. If G is a petal graph and w is a vertex of G of degree two having neighbours v1 v2 then the path Pw v1wv2 is a petal of G. We name w the centre of the petal and v1 v2 the basepoints. By property 3 the basepoints of the petal Pw are in Ga. If disÌGÁ v1 v2 k we say that
