Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts
| dc.creator | Rabern, Landon | |
| dc.date | 2005-12-13 | |
| dc.date | 2006-01-10 | |
| dc.date.accessioned | 2026-07-07T06:55:11Z | |
| dc.date.available | 2026-07-07T06:55:11Z | |
| dc.description | 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 $χ(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 $ω$ and $χ$; namely, the graph parameters $A_r(G) = (1-r) ω(G) + r χ(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}. | |
| dc.identifier | https://arxiv.org/abs/math/0512291 | |
| dc.identifier | http://arxiv.org/abs/math/0512291 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/106200 | |
| dc.subject | Combinatorics | |
| dc.title | Some bounds on convex combinations of $ω$ and $χ$ for decompositions into many parts | |
| dc.type | text |