pith. sign in

arxiv: math/0512291 · v5 · submitted 2005-12-13 · 🧮 math.CO

Some bounds on convex combinations of ω and chi for decompositions into many parts

classification 🧮 math.CO
keywords omegagraphcombinationsconvexdecompositiondecompositionskostochkasome
0
0 comments X
read the original abstract

A \emph{$k$--decomposition} of the complete graph $K_n$ is a decomposition of $K_n$ into $k$ spanning subgraphs $G_1,...,G_k$. For a graph parameter $p$, let $p(k;K_n)$ denote the maximum of $\displaystyle \sum_{j=1}^{k} p(G_j)$ over all $k$--decompositions of $K_n$. It is known that $\chi(k;K_n) = omega(k;K_n)$ for $k \leq 3$ and conjectured that this equality holds for all $k$. In an attempt to get a handle on this, we study convex combinations of $\omega$ and $\chi$; namely, the graph parameters $A_r(G) = (1-r) \omega(G) + r \chi(G)$ for $0 \leq r \leq 1$. It is proven that $A_r(k;K_n) \leq n + {k \choose 2}$ for small $r$. In addition, we prove some generalizations of a theorem of Kostochka, et al. \cite{kostochka}.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.