Cubic Graphs, Disjoint Matchings and Some Inequalities
Lianna Hambardzumyan, Vahan Mkrtchyan · arXiv (Cornell University) · 2015
For $k = 2,3$ and a cubic graph $G$ let $ u_k(G)$ denote the size of a maximum $k$-edge-colorable subgraph of $G$. Mkrtchyan, Petrosyan and Vardanyan proved that $ u_2(G)\geq \frac45\cdot |V(G)|$, $ u_3(G)\geq \frac76\cdot |V(G)|$ ~\cite{samvel:2010}. They were also able to show that $ u_2(G)+ u_3(G)\geq 2\cdot |V(G)|$ ~\cite{samvel:2014} and $ u_2(G) \leq \frac{|V(G)| + 2\cdot u_3(G)}{4}$ ~\cite{samvel:2010}. In the present work, we show that the last two inequalities imply the first two of them. Moreover, we show that $ u_2(G) \geq \alpha \cdot \frac{|V(G)| + 2\cdot u_3(G)}{4} $, where $\alpha=\frac{16}{17}$, if $G$ is a cubic graph, $\alpha=\frac{20}{21}$, if $G$ is a cubic graph containing a perfect matching, $\alpha=\frac{44}{45}$, if $G$ is a bridgeless cubic graph. Finally, we investigate the parameters $ u_2(G)$ and $ u_3(G)$ in the class of claw-free cubic graphs. We improve the lower bounds for $ u_2(G)$ and $ u_3(G)$ for claw-free bridgeless cubic graphs to $ u_2(G)\geq \frac{29}{30}\cdot |V(G)|$, $ u_3(G)\geq \frac{43}{45}\cdot |E(G)|$. We also show that $ u_2(G) \geq \frac{35}{36} \cdot |V(G)|$ when $n \geq 48$. On the basis of these inequalities we are able to improve the coefficient $\alpha$ for bridgeless claw-free cubic graphs.