Achromatic number of collections of paths and cycles

Keith J. Edwards

doi:10.1016/j.disc.2012.08.008

Achromatic number of collections of paths and cycles

Research output: Contribution to journal › Article › peer-review

Abstract

A complete colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at least one edge. The achromatic number ?(G) is the greatest number of colours in such a colouring.
We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph.

Original language	English
Pages (from-to)	1856–1860
Number of pages	5
Journal	Discrete Mathematics
Volume	313
Issue number	19
DOIs	https://doi.org/10.1016/j.disc.2012.08.008
Publication status	Published - 6 Oct 2013

Keywords

Achromatic number
Cycles
Paths

Access to Document

10.1016/j.disc.2012.08.008

Cite this

@article{faa9862dd40747639fcbfda47e39dca7,

title = "Achromatic number of collections of paths and cycles",

abstract = "A complete colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at least one edge. The achromatic number ?(G) is the greatest number of colours in such a colouring. We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph. ",

keywords = "Achromatic number , Cycles , Paths",

author = "Edwards, \{Keith J.\}",

year = "2013",

month = oct,

day = "6",

doi = "10.1016/j.disc.2012.08.008",

language = "English",

volume = "313",

pages = "1856–1860",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "19",

}

TY - JOUR

T1 - Achromatic number of collections of paths and cycles

AU - Edwards, Keith J.

PY - 2013/10/6

Y1 - 2013/10/6

N2 - A complete colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at least one edge. The achromatic number ?(G) is the greatest number of colours in such a colouring. We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph.

AB - A complete colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at least one edge. The achromatic number ?(G) is the greatest number of colours in such a colouring. We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph.

KW - Achromatic number

KW - Cycles

KW - Paths

UR - http://www.scopus.com/inward/record.url?scp=84865455757&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2012.08.008

DO - 10.1016/j.disc.2012.08.008

M3 - Article

AN - SCOPUS:84865455757

SN - 0012-365X

VL - 313

SP - 1856

EP - 1860

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 19

ER -

Achromatic number of collections of paths and cycles

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this