Enumerating the edge-colourings and total colourings of a regular graph | Journal of Combinatorial Optimization Skip to main content
Springer Nature Link
Log in

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

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k⋅((k−1)!)n/2. Our proof is constructive and leads to a branching algorithm enumerating all the k-edge-colourings of a connected k-regular graph in time O ∗(((k−1)!)n/2) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O ∗(2n/2)=O ∗(1.4143n) and polynomial space. This improves the running time of O ∗(1.5423n) of the algorithm due to Golovach et al. (Proceedings of WG 2010, pp. 39–50, 2010). We also show that the number of 4-total-colourings of a connected cubic graph is at most 3⋅23n/2. Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph.

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

  • Alon N, Friedland S (2008) The maximum number of perfect matchings in graphs with a given degree sequence. Electron J Comb 15:N13

    MathSciNet  Google Scholar 

  • Beigel R, Eppstein D (2005) 3-coloring in time O(1.3289n). J Algorithms 54:168–204

    Article  MathSciNet  MATH  Google Scholar 

  • Björklund A, Husfeldt T (2006) Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of the 47th annual IEEE symposium on foundations of computer science (FOCS 2006). IEEE Comput. Soc., Los Alamitos, pp 575–582

    Chapter  Google Scholar 

  • Björklund A, Husfeldt T, Koivisto M (2009) Set partitioning via Inclusion-Exclusion. SIAM J Comput 39(2):546–563

    Article  MathSciNet  MATH  Google Scholar 

  • Björklund A, Husfeldt T, Kaski P, Koivisto M (2010) Narrow sieves for parameterized paths and packings. arXiv:1007.1161v1

  • Bondy JA, Murty USR (2008) Graph theory, 2nd edn. Graduate texts in mathematics, vol 244. Springer, Berlin

    Book  MATH  Google Scholar 

  • Bregman LM (1973) Some properties of nonnegative matrices and their permanents. Sov Math Dokl 14:945–949

    MATH  Google Scholar 

  • Even S, Tarjan RE (1976) Computing an st-numbering. Theor Comput Sci 2(3):339–344

    Article  MathSciNet  MATH  Google Scholar 

  • Even S, Tarjan RE (1977) Corrigendum: Computing an st-numbering. Theor Comput Sci 4(1):123

    Article  MathSciNet  Google Scholar 

  • Fomin FV, Gaspers S, Saurabh S (2007) Improved exact algorithms for counting 3- and 4-colorings. In: Lin G (ed) COCOON 2007. Lecture notes in computer science, vol 4598, pp 65–74

    Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences. Freeman, San Francisco

    MATH  Google Scholar 

  • Golovach PA, Kratsch D, Couturier JF (2010) Colorings with few colors: counting, enumeration and combinatorial bounds. In: Proceedings of WG 2010. Lecture notes in computer science, vol 6410, pp 39–50

    Google Scholar 

  • Holyer I (1981) The NP-completeness of edge-colouring. SIAM J Comput 2:225–231

    Article  Google Scholar 

  • Jensen TR, Toft B (1995) Graph coloring problems. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York

    MATH  Google Scholar 

  • Knuth DE (2011) The art of computer programming, vol 4A. Combinatorial algorithms, Part 1. Addison-Wesley, Reading

    Google Scholar 

  • Koivisto M (2006) An O(2n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: Proceedings of the 47th annual IEEE symposium on foundations of computer science (FOCS 2006). IEEE Comput. Soc., Los Alamitos, pp 583–590

    Chapter  Google Scholar 

  • Kowalik L (2009) Improved edge-coloring with three colors. Theor Comput Sci 410:3733–3742

    Article  MathSciNet  MATH  Google Scholar 

  • Lempel A, Even S, Cederbaum I (1967) An algorithm for planarity testing of graphs. In: Rosenstiehl P (ed) Proceedings of the international symposium on the theory of graphs, Rome, July 1966. Gordon & Breach, New York, pp 215–232

    Google Scholar 

  • Sánchez-Arroyo A (1989) Determining the total colouring number is NP-hard. Discrete Math 78(3):315–319

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgement

The authors would like to thank their children for suggesting them some graph names.

Author information

Authors and Affiliations

  1. Université Montpellier 2—CNRS, LIRMM, Montpellier, France

    S. Bessy

  2. Projet Mascotte, I3S (CNRS, UNSA) and INRIA, Sophia Antipolis, France

    F. Havet

Authors
  1. S. Bessy
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. F. Havet
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to F. Havet.

Additional information

This work is supported by the French Agence Nationale de la Recherche under reference AGAPE ANR-09-BLAN-0159.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bessy, S., Havet, F. Enumerating the edge-colourings and total colourings of a regular graph. J Comb Optim 25, 523–535 (2013). https://doi.org/10.1007/s10878-011-9448-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-011-9448-5

Keywords