Chromaticity of Complete 5-Partite Graphs with Certain Star or Matching Deleted

Ameen Shaman Ameen, Yee Hock Peng, Haixing Zhao, Gee Choon Lau, Roslan Hasni

Abstract


Let P(G, \lambda) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted by G ∼ H, if P(G,\lambda ) = P(H,\lambda ). We write [G] = {H|H ∼ G}. If [G] = {G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 5-partite graphs with 5n + 1 vertices according to the number of 6-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 5-partite graphs with certain star or matching deleted are obtained.

Full Text: PDF

Refbacks

  • There are currently no refbacks.


The Thai Journal of Mathematics organized and supported by The Mathematical Association of Thailand and Thailand Research Council and the Center for Promotion of Mathematical Research of Thailand (CEPMART).

Copyright 2020 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|