Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 4/2013

01.05.2013

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

verfasst von: Jean-Francois Couturier, Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Artem Pyatkin

Erschienen in: Theory of Computing Systems | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree.
This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided.
The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.
Vorheriger Artikel The Rank-Width of Edge-Coloured Graphs
Nächster Artikel Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
For the purpose of this paper we shall address L(2,1)-labeling as a coloring problem.
 
2
As has recently become standard, we write f(n)=O ∗(g(n)) if f(n)≤p(n)⋅g(n) for some polynomial p(n).
 
3
Motivated by a presentation of the edge coloring results of our work, published in [18], in a talk given by D. Kratsch at a meeting of the AGAPE project in January 2011, S. Bessy and F. Havet first (during the meeting) established the maximum number of edge 3-colorings in cubic graphs, and then extended this in various directions [4]. Let us mention that their work improves upon our enumeration algorithms for edge 3-colorings and total 4-colorings of connected cubic graphs and the corresponding combinatorial upper bounds given in Sect. 3; they study neither the L(2,1)-labeling problem nor counting versions of the problems.
 
4
The auxiliary graph H is the only multigraph of the paper and its only purpose is to ease the description of the example.
 
Literatur
1.
Alon, N., Friedland, S.: The maximum number of perfect matchings in graphs with a given degree sequence. Electron. J. Comb. 15, N13 (2008) MathSciNet
2.
Alon, N., Rödl, V., Rucinski, A.: Perfect matchings in ϵ-regular graphs. Electron. J. Comb. 5, R13 (1998)
3.
4.
5.
Björklund, A., Husfeldt, T.: Inclusion–exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 575–582. IEEE, New York (2006) CrossRef
6.
Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms 11, 631–643 (1990) MathSciNetMATHCrossRef
7.
Bregman, L.M.: Some properties of nonnegative matrices and their permanents. Sov. Math. Dokl. 14, 945–949 (1973) MATH
8.
Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 329–337. SIAM, Philadelphia (2001)
9.
Fiala, J., Kloks, T., Kratochvíl, J.: Fixed-parameter complexity of lambda-labelings. Discrete Appl. Math. 113, 59–72 (2001) MathSciNetMATHCrossRef
10.
Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3- and 4-colorings. In: COCOON 2007. Lecture Notes in Computer Science, vol. 4598, pp. 65–74. Springer, Berlin (2007)
11.
Fomin, F.V., Gaspers, S., Saurabh, S.: On two techniques of combining branching and treewidth. Algorithmica 54, 181–207 (2009) MathSciNetMATHCrossRef
12.
Fomin, F., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 47–77 (2005) MathSciNetMATH
13.
Fomin, F.V., Grandoni, F., Pyatkin, A., Stepanov, A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9 (2008) MathSciNetCrossRef
14.
Fomin, F.V., Høie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97, 191–196 (2006) MATHCrossRef
15.
Fomin, F.V., Kratsch, D.: Exact exponential algorithms. In: Texts in Theoretical Computer Science. Springer, Berlin (2010)
16.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979) MATH
17.
18.
Golovach, P.A., Kratsch, D., Couturier, J.F.: Colorings with few colors: counting, enumeration and combinatorial bounds. In: Thilikos, D. (ed.) Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Computer Science, vol. 6410, pp. 39–50. Springer, Berlin (2010)
19.
Havet, F., Klazar, M., Kratochvíl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2,1)-labeling of graphs. Algorithmica 59, 169–194 (2011) MathSciNetMATHCrossRef
20.
21.
Junosza-Szaniawski, K., Kratochvíl, J., Liedloff, M., Rossmanith, P., Rzazewski, P.: Fast exact algorithm for L(2,1)-labeling of graphs. In: Ogihara, M., Tarui, J. (eds.) Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Lecture Notes in Computer Science, vol. 6648, pp. 82–93. Springer, Berlin (2011) CrossRef
22.
Junosza-Szaniawski, K., Rzazewski, P.: On improved exact algorithms for L(2,1)-labeling of graphs. In: Iliopoulos, C.S., Smyth, W.F. (eds.) Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010). Lecture Notes in Computer Science, vol. 6460, pp. 34–37. Springer, Berlin (2010) CrossRef
23.
Junosza-Szaniawski, K., Rzazewski, P.: On the complexity of exact algorithm for L(2,1)-labeling of graphs. Inf. Process. Lett. 111, 697–701 (2011) MathSciNetMATHCrossRef
24.
Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994) MATHCrossRef
25.
Koivisto, M.: An O(2 n ) 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), pp. 583–590. IEEE, New York (2006) CrossRef
26.
27.
28.
29.
30.
31.
32.
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskretn. Anal. 3, 25–30 (1964) (in Russian) MathSciNet
33.
Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization—Eureka, You Shrink! Lecture Notes in Computer Science, vol. 2570, pp. 185–207. Springer, Berlin (2003) CrossRef
34.
Zhou, X., Nishizeki, T.: Optimal parallel algorithm for edge-coloring partial k-trees with bounded degrees. In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, pp. 167–174. IEEE, New York (1994) CrossRef
35.
Metadaten
Titel
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
verfasst von
Jean-Francois Couturier
Petr A. Golovach
Dieter Kratsch
Mathieu Liedloff
Artem Pyatkin
Publikationsdatum
01.05.2013
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 4/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-012-9410-7

Weitere Artikel der Ausgabe 4/2013

Theory of Computing Systems 4/2013 Zur Ausgabe

OriginalPaper

Built-in Coloring for Highly-Concurrent Doubly-Linked Lists

OriginalPaper

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

OriginalPaper

Parameterized Complexity of Satisfying Almost All Linear Equations over

OriginalPaper

On Rationality of Verbal Subsets in a Group

OriginalPaper

Collusion in Atomic Splittable Routing Games

OriginalPaper

Partition Into Triangles on Bounded Degree Graphs