A new bound for parsimonious edge-colouring of graphs with maximum degree three

Details A new bound for parsimonious edge-colouring of graphs with maximum degree three A new bound for parsimonious edge-colouring of graphs with maximum degree three

2011-02-27

arxiv.org/abs/1102.5523v1

Computer Science

Discrete Mathematics

Scientific paper

In a graph $G$ of maximum degree 3, let $\gamma(G)$ denote the largest fraction of edges that can be 3 edge-coloured. Rizzi \cite{Riz09} showed that $\gamma(G) \geq 1-\frac{2\strut}{\strut 3 g_{odd}(G)}$ where $g_{odd}(G)$ is the odd girth of $G$, when $G$ is triangle-free. In \cite{FouVan10a} we extended that result to graph with maximum degree 3. We show here that $\gamma(G) \geq 1-\frac{2 \strut}{\strut 3 g_{odd}(G)+2}$, which leads to $\gamma(G) \geq 15/17$ when considering graphs with odd girth at least 5, distinct from the Petersen graph.

Affiliated with

Also associated with

No associations

Rating

A new bound for parsimonious edge-colouring of graphs with maximum degree three 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 A new bound for parsimonious edge-colouring of graphs with maximum degree three, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new bound for parsimonious edge-colouring of graphs with maximum degree three will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54128