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

Details Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts

2005-12-13

arxiv.org/abs/math/0512291v5

Mathematics

Combinatorics

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81715