اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA new polynomial on compositions of integers: on distinguishing caterpillars from their symmetric chromatic function
123
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we propose an algebraic approach to determine whether two non-isomorphic caterpillar trees can have the same symmetric function generalization of the chromatic polynomial. On the set of all composition on integers, we introduce: An operation, which we call composition product; and a combinatorial polynomial, which we call the composition-lattice polynomial or L-polynomial, that mimics the weighted graph polynomial of Noble and Welsh. We prove a unique irreducible factorization theorem and establish a connection between the L-polynomial of a composition and its irreducible factorization, namely that reversing irreducible factors does not change L, and conjecture that is the only way of generating such compositions. Finally, we find a sufficient condition for two caterpillars have a different symmetric function generalization of the chromatic polynomial, and use this condition to show that if our conjecture were to hold, then the symmetric function generalization of the chromatic polynomial distinguishes among a large class of caterpillars.
قيم البحث
اقرأ أيضاً
This paper deals with the so-called Stanley conjecture, which asks whether they are non-isomorphic trees with the same symmetric function generalization of the chromatic polynomial. By establishing a correspondence between caterpillars trees and inte
ger compositions, we prove that caterpillars in a large class (we call trees in this class proper) have the same symmetric chromatic function generalization of the chromatic polynomial if and only if they are isomorphic.
This paper has two main parts. First, we consider the Tutte symmetric function $XB$, a generalization of the chromatic symmetric function. We introduce a vertex-weighted version of $XB$ and show that this function admits a deletion-contraction relati
on. We also demonstrate that the vertex-weighted $XB$ admits spanning-tree and spanning-forest expansions generalizing those of the Tutte polynomial by connecting $XB$ to other graph functions. Second, we give several methods for constructing nonisomorphic graphs with equal chromatic and Tutte symmetric functions, and use them to provide specific examples.
We define a bivariate polynomial for unlabeled rooted trees and show that the polynomial of an unlabeled rooted tree $T$ is the generating function of a class of subtrees of $T$. We prove that the polynomial is a complete isomorphism invariant for un
labeled rooted trees. Then, we generalize the polynomial to unlabeled unrooted trees and we show that the generalized polynomial is a complete isomorphism invariant for unlabeled unrooted trees.
An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing colori
ng of G is denoted by $chi_a(G)$. In this paper, we prove that $chi_a(G)$ <= 5($Delta+2$)/2 for any graph G having maximum degree $Delta$ and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006), 3005-3010], which states that $chi_a(G)$ <= 3$Delta$ for any graph G without isolated edges.
In this note we obtain a new bound for the acyclic edge chromatic number $a(G)$ of a graph $G$ with maximum degree $D$ proving that $a(G)leq 3.569(D-1)$. To get this result we revisit and slightly modify the method described in [Giotis, Kirousis, Psa
romiligkos and Thilikos, Theoretical Computer Science, 66: 40-50, 2017].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
