1990 | OriginalPaper | Chapter
Extending Hall’s Theorem
Authors : A. J. W. Hilton, P. D. Johnson Jr.
Published in: Topics in Combinatorics and Graph Theory
Publisher: Physica-Verlag HD
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let G be a finite simple graph. Suppose that to each vertex v ∈ V(G) there is assigned a finite set (or “list”) C(v) of colours (or “symbols”). The general problem is: what conditions on G and the colour-set assignment C guarantee that the vertices of G can be coloured so that each v ∈ V(G) is coloured with a colour from C(v), and adjacent vertices are coloured differently? Such a colouring of V(G) will be called a C-colouring of G.