On parsimonious edge-colouring of graphs with maximum degree three

DOI10.1007/S00373-012-1145-3MaRDI QIDQ2376086zbMATH OpenOpenAlexFDO

Authors Jean-Luc Fouquet, Jean-Marie Vanherpe

Publication date 26 June 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.4747

zbMATH Keywords

cubic graphedge-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: In a graph $G$ of maximum degree $Delta$ let $gamma$ denote the largest fraction of edges that can be $Delta$ edge-coloured. Albertson and Haas showed that $gammageq13/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=13/15$. This extends a result given by Steffen. These results are obtained by using structural properties of the so called $delta$-minimum edge colourings for graphs with maximum degree 3. Keywords : Cubic graph; Edge-colouring

Recommendations

• Parsimonious edge coloring
• Approximating the maximum 3-edge-colorable subgraph problem
• Maximum edge-colorings of graphs
• Variations on the Petersen colouring conjecture
• On list edge-colorings of subcubic graphs

Cites work

• Approximating the maximum 3-edge-colorable subgraph problem
• Classification and characterizations of snarks
• Graphes Cubiques D'Indice Chromatique Quatre
• scientific article; zbMATH DE number 3706475 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• Measurements of edge-uncolorability
• On parsimonious edge-colouring of graphs with maximum degree three
• Parsimonious edge coloring

Cited in

(19)

• Precoloring extension for 2-connected graphs with maximum degree three
• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• On S-packing edge-colorings of cubic graphs
• On S-packing edge-colorings of graphs with small edge weight
• On parsimonious edge-colouring of graphs with maximum degree three
• Covering a cubic graph with perfect matchings
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On Sylvester colorings of cubic graphs
• Parsimonious edge-coloring on surfaces
• Between Proper and Strong Edge-Colorings of Subcubic Graphs
• On the maximal triangle-free edge-chromatic graphs in three colors
• Between proper and strong edge‐colorings of subcubic graphs
• Graphs, disjoint matchings and some inequalities
• The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
• Measures of edge-uncolorability of cubic graphs
• On S-packing edge-coloring of graphs with given edge weight
• Claw-free cubic graphs are (1, 1, 1, 3)-packing edge-colorable
• On S-packing edge-colorings of subcubic claw-free graphs
• On the excessive \([m]\)-index of a tree

This page was built for publication: On parsimonious edge-colouring of graphs with maximum degree three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376086)