On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three

详细信息    查看全文

• 作者：J.-L. Fouquet (1)
  J.-M. Vanherpe (1)
  
• 关键词：Cubic graph ; Edge ; colouring ; 05C15
• 刊名：Graphs and Combinatorics
• 出版年：2013
• 出版时间：May 2013
• 年：2013
• 卷：29
• 期：3
• 页码：475-487
• 全文大小：233KB
• 参考文献：1. Albertson M.O., Haas R.: Parsimonious edge colouring. Discret. Math. 148, 1- (1996) CrossRef
  2. Bondy J.A., Locke S.: Largest bipartite subgraphs in triangle free graphs with maximum degree three. J. Graph Theory 10, 477-04 (1986) jgt.3190100407">CrossRef
  3. Fouquet J.-L.: Graphes cubiques d’indice chromatique quatre. Ann. Discret. Math. 9, 23-8 (1980) CrossRef
  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-39 (1975) CrossRef
  8. K?nig D.: über Graphen und ihre Anwendung auf Determinantentheorie un Mengenlehre. Math. Ann. 77, 453-65 (1916) CrossRef
  9. Locke S.C.: Maximum / k-colourable subgraphs. J. Graph Theory 6, 123-32 (1982) jgt.3190060206">CrossRef
  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-170 (2009) j.disc.2008.11.017">CrossRef
  12. Staton W.: Edge deletions and the chromatic number. Ars Combin. 10, 103-06 (1980)
  13. Steffen E.: Classifications and characterizations of snarks. Discret. Math. 188, 183-03 (1998) CrossRef
  14. Steffen E.: Measurements of edge-uncolorability. Discret. Math. 280, 191-14 (2004) j.disc.2003.05.005">CrossRef
  15. Vizing V.G.: On an estimate of the chromatic class of a / p-graph. Diskret. Analiz. 3, 25-0 (1964)
  
• 作者单位：J.-L. Fouquet (1)
  J.-M. Vanherpe (1)
  
  1. L.I.F.O., Faculté des Sciences, Université d’Orléans, B.P. 6759, 45067, Orléans Cedex 2, France
  
• ISSN：1435-5914

文摘

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.