New result on chromaticity of K₄-homeomorphic graphs

Abstract

A K₄-homeomorphic graph or simply K₄-homeomorph, denoted by K₄(a, b, c, d, e, f), is the graph obtained when the six edges of a complete graph with four vertices (K₄) are subdivided into a, b, c, d, e, f segments, respectively. Each subdivided edge is called a path and its length is the number of resulting segments. The result in this paper completes the study on the chromaticity of K₄-homeomorphs with exactly two paths of length 2.

Keywords:

• chromatic polynomial
• chromatic uniqueness
• K₄-homeomorphic graphs

2000 AMS Subject Classification:

• Primary: 05C15

Acknowledgements

The authors would like to extend their sincere thanks to the referees for their constructive and valuable comments.