Non-bipartite chromatic factors

详细信息    查看全文

• 作者：Kerri Morgan ; ^{Kerri.Morgan@monash.edu} ; Graham Farr ^{Graham.Farr@monash.edu}
• 关键词：Chromatic polynomial ; Chromatic factorisation ; Chromatic factors
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：28 March, 2012
• 年：2012
• 卷：312
• 期：6
• 页码：1166-1170
• 全文大小：321 K

文摘

The chromatic polynomial gives the number of proper colourings of a graph in at most colours. If , then is said to have a chromatic factorisation of order with chromatic factors and . It is clear that, if , any with chromatic number is the chromatic factor of some chromatic factorisation of order . We show that every with , even when contains no triangles, is the chromatic factor of some chromatic factorisation of order and give a certificate of factorisation for this chromatic factorisation. This certificate shows in a sequence of seven steps using some basic properties of chromatic polynomials that a graph has a chromatic factorisation with one of the chromatic factors being . This certificate is one of the shortest known certificates of factorisation, excluding the trivial certificate for chromatic factorisations of clique-separable graphs.