Browsing by Subject "chromatic polynomial"

Now showing 1 - 3 of 3

Access status: Open Access ,
Colourings of (k-r,k)-trees
(Wydawnictwa AGH, 2017) Borowiecki, Mieczysław; Patil, H.P.
Trees are generalized to a special kind of higher dimensional complexes known as $(j,k)$-trees ([L. W. Beineke, R. E. Pippert, On the structure of $(m,n)$-trees, Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, 75-80]), and which are a natural extension of $k$-trees for $j=k−1$. The aim of this paper is to study$(k−r,k)$-trees ([H. P. Patil, Studies on $k$-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984]), which are a generalization of $k$-trees (or usual trees when $k=1$). We obtain the chromatic polynomial of $(k−r,k)$-trees and show that any two $(k−r,k)$-trees of the same order are chromatically equivalent. However, if $r\neq 1$ in any $(k−r,k)$-tree $G$, then it is shown that there exists another chromatically equivalent graph $H$, which is not a $(k−r,k)$-tree. Further, the vertex-partition number and generalized total colourings of $(k−r,k)$-trees are obtained. We formulate a conjecture about the chromatic index of $(k−r,k)$-trees, and verify this conjecture in a number of cases. Finally, we obtain a result of [M. Borowiecki, W. Chojnacki, Chromatic index of $k$-trees, Discuss. Math. 9 (1988), 55-58] as a corollary in which $k$-trees of Class 2 are characterized.
Access status: Open Access ,
On chromatic equivalence of a pair of K4-homeomorphs
(Wydawnictwa AGH, 2010) Catada-Ghimire, S.; Roslan, H.; Peng, Yee-hock
Let $P(G, \lambda)$ be the chromatic polynomial of a graph $G$. Two graphs $G$ and $H$ are said to be chromatically equivalent, denoted $G∼H$, if $PP(G, \lambda)=P(H, \lambda)$. We write $[G] = \{H| H \sim G\}$. If $[G] = \{G\}$, then $G$ is said to be chromatically unique. In this paper, we discuss a chromatically equivalent pair of graphs in one family of $K_{4}$-homeomorphs, $K_{4}(1,2,8,d,e,f)$. The obtained result can be extended in the study of chromatic equivalence classes of $K_{4}(1,2,8,d,e,f)$ and chromatic uniqueness of $K_{4}$-homeomorphs with girth $11$.
Access status: Restricted ,
Współczynniki wielomianu chromatycznego
(Data obrony: 2009-07-01) Urbaniak, Emilia
Wydział Matematyki Stosowanej