On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three | Graphs and Combinatorics
Skip to main content
Springer Nature Link
Log in

On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In a graph G of maximum degree Δ, let γ denote the largest fraction of edges that can be Δ edge-coloured. Albertson and Haas showed that \({\gamma \geq \frac{13}{15}}\) when G is cubic. We show here that this result can be extended to graphs with maximum degree 3, with the exception of a graph on 5 vertices. Moreover, there are exactly two graphs with maximum degree 3 (one being obviously the Petersen graph) for which \({\gamma = \frac{13}{15}.}\) This extends a result given by Steffen. These results are obtained by using structural properties of the so called δ-minimum edge colourings for graphs with maximum degree 3.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albertson M.O., Haas R.: Parsimonious edge colouring. Discret. Math. 148, 1–7 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bondy J.A., Locke S.: Largest bipartite subgraphs in triangle free graphs with maximum degree three. J. Graph Theory 10, 477–504 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  3. Fouquet J.-L.: Graphes cubiques d’indice chromatique quatre. Ann. Discret. Math. 9, 23–28 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  4. Fouquet, J.-L.: Contribution à à l’ étude des graphes cubiques et problèmes hamiltoniens dans les graphes orientés. Ph.D. thesis, Université Paris SUD (1981)

  5. Fouquet, J.-L., Vanherpe, J.-M.: A new bound for parsimonious edge-colouring of graphs with maximum degree three (2011). http://hal.archives-ouvertes.fr/hal-00516702/PDF/Parcimonious_15_17_Version_27_Feb_2011--.pdf

  6. Fouquet, J.-L., Vanherpe, J.-M.: Tools for parsimonious edge-colouring of graphs with maximum degree three (2012). http://hal.archives-ouvertes.fr/hal-00502201/PDF/ToolsForParcimoniousColouring_Revision4_HAL.pdf

  7. Isaacs R.: Infinite families of non-trivial trivalent graphs which are not Tait colorable. Am. Math. Mon. 82, 221–239 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  8. König D.: Über Graphen und ihre Anwendung auf Determinantentheorie un Mengenlehre. Math. Ann. 77, 453–465 (1916)

    Article  MathSciNet  MATH  Google Scholar 

  9. Locke S.C.: Maximum k-colourable subgraphs. J. Graph Theory 6, 123–132 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  10. Payan, C.: Sur quelques problèmes de couverture et de couplage en combinatoire. Thèse d’état (1977)

  11. Rizzi R.: Approximating the maximum 3-edge-colorable subgraph problem. Discret. Math. 309(12), 4166–4170 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Staton W.: Edge deletions and the chromatic number. Ars Combin. 10, 103–106 (1980)

    MathSciNet  MATH  Google Scholar 

  13. Steffen E.: Classifications and characterizations of snarks. Discret. Math. 188, 183–203 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  14. Steffen E.: Measurements of edge-uncolorability. Discret. Math. 280, 191–214 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  15. Vizing V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30 (1964)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. L.I.F.O., Faculté des Sciences, Université d’Orléans, B.P. 6759, 45067, Orléans Cedex 2, France

    J.-L. Fouquet & J.-M. Vanherpe

Authors
  1. J.-L. Fouquet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J.-M. Vanherpe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J.-M. Vanherpe.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fouquet, JL., Vanherpe, JM. On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three. Graphs and Combinatorics 29, 475–487 (2013). https://doi.org/10.1007/s00373-012-1145-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1145-3

Keywords

Mathematics Subject Classification (2000)

Search

Navigation