Enumerating the edge-colourings and total colourings of a regular graph

DOI10.1007/s10878-011-9448-5zbMath1271.05050OpenAlexW2118902335MaRDI QIDQ1956248

Frédéric Havet, Stéphane Bessy

Publication date: 13 June 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-00821598/file/3aretecol.pdf

zbMATH Keywords

enumerationregular graphedge colouringtotal colouring\((s,t)\)-ordering

Mathematics Subject Classification ID

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

Related Items (6)

A note on the minimum number of choosability of planar graphs ⋮ Switching 3-edge-colorings of cubic graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ An efficient case for computing minimum linear arboricity with small maximum degree ⋮ Minimum number of disjoint linear forests covering a planar graph ⋮ Optimal channel assignment with list-edge coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved edge-coloring with three colors
• Determining the total colouring number is NP-hard
• The maximum number of perfect matchings in graphs with a given degree sequence
• Computing an st-numbering
• Narrow sieves for parameterized paths and packings
• Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds
• Set Partitioning via Inclusion-Exclusion
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Algorithms and Data Structures for Sparse Symmetric Gaussian Elimination
• 3-coloring in time

This page was built for publication: Enumerating the edge-colourings and total colourings of a regular graph