Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 7/2020

08-04-2020

Complexity of Fall Coloring for Restricted Graph Classes

Authors: Juho Lauri, Christodoulos Mitillos

Published in: Theory of Computing Systems | Issue 7/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We strengthen a result by Laskar and Lyle (Discrete Appl. Math. 157, 330–338 2009) by proving that it is NP-complete to decide whether a bipartite planar graph can be partitioned into three independent dominating sets. In contrast, we show that this is always possible for every maximal outerplanar graph with at least three vertices. Moreover, we extend their previous result by proving that deciding whether a bipartite graph can be partitioned into k independent dominating sets is NP-complete for every k ≥ 3. We also strengthen a result by Henning et al. (Discrete Math. 309(23), 6451–6458 2009) by showing that it is NP-complete to determine if a graph has two disjoint independent dominating sets, even when the problem is restricted to triangle-free planar graphs. Finally, for every k ≥ 3, we show that there is some constant t depending only on k such that deciding whether a k-regular graph can be partitioned into t independent dominating sets is NP-complete. We conclude by deriving moderately exponential-time algorithms for the problem.
previous article Parameterized Complexity of Min-Power Asymmetric Connectivity
next article On the Average Case of MergeInsertion

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
1.
de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. International Journal of Computational Geometry & Applications 22(03), 187–205 (2012)MathSciNetCrossRef
2.
Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546–563 (2009)MathSciNetCrossRef
3.
Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNetCrossRef
4.
Bodlaender, H. L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)MathSciNetCrossRef
5.
Chartrand, G., Geller, D. P.: On uniquely colorable planar graphs. Journal of Combinatorial Theory 6(3), 271–278 (1969)MathSciNetCrossRef
6.
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation 85(1), 12–75 (1990)MathSciNetCrossRef
7.
Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)MATH
8.
Dunbar, J. E., Hedetniemi, S. M., Hedetniemi, S., Jacobs, D. P., Knisely, J., Laskar, R., Rall, D. F.: Fall colorings of graphs. J. Comb. Math. Comb. Comput. 33, 257–274 (2000)MathSciNetMATH
9.
Fomin, F. V., Thilikos, D. M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory 51(1), 53–81 (2006)MathSciNetMATH
10.
Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)MathSciNetMATH
11.
Goddard, W., Henning, M. A.: Independent domination in graphs: a survey and recent results. Discret. Math. 313(7), 839–854 (2013)MathSciNetMATH
12.
Golumbic, M. C.: Algorithmic graph theory and perfect graphs. Elsevier (2004)
13.
Heggernes, P., Telle, J. A.: Partitioning graphs into generalized dominating sets. Nordic Journal of Computing 5(2), 128–142 (1998)MathSciNetMATH
14.
Henning, M. A., Lȯwenstein, C., Rautenbach, D.: Remarks about disjoint dominating sets. Discret. Math. 309(23), 6451–6458 (2009)MathSciNetMATH
15.
Kaul, H., Mitillos, C.: On graph fall-coloring: Operators and heredity. J. Comb. Math. Comb. Comput. 106, 125–151 (2018)MathSciNetMATH
16.
Kaul, H., Mitillos, C.: On graph fall-coloring: Existence and constructions. Graphs and Combinatorics 35(6), 1633–1646 (2019)MathSciNetMATH
17.
Laskar, R., Lyle, J.: Fall colouring of bipartite graphs and cartesian products of graphs. Discret. Appl. Math. 157(2), 330–338 (2009)MathSciNetMATH
18.
Leven, D., Galil, Z.: NP-Completeness of finding the chromatic index of regular graphs. Journal of Algorithms 4(1), 35–44 (1983)MathSciNetMATH
19.
Lewis, R.: A Guide to Graph Colouring. Springer, Berlin (2015)
20.
Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discret. Math. 162(1-3), 313–317 (1996)MathSciNetMATH
21.
Marx, D.: Graph colouring problems and their applications in scheduling. Electr. Eng. 48(1-2), 11–16 (2004)
22.
Mitillos, C.: Topics in graph fall-coloring. Ph.D. thesis, Illinois Institute of Technology (2016)
23.
Resende, M. G., Pardalos, P.M.: Handbook of optimization in telecommunications. Springer Science & Business Media, Berlin (2008)MATH
24.
van Rooij, J. M. M., Bodlaender, H. L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 5757, pp 566–577. Springer (2009)
25.
Telle, J. A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discret. Math. 10, 529–550 (1997)MathSciNetMATH
Metadata
Title
Complexity of Fall Coloring for Restricted Graph Classes
Authors
Juho Lauri
Christodoulos Mitillos
Publication date
08-04-2020
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 7/2020
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-020-09982-9

Other articles of this Issue 7/2020

Theory of Computing Systems 7/2020 Go to the issue

OriginalPaper

Computing the k-Visibility Region of a Point in a Polygon

OriginalPaper

Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings

OriginalPaper

Complexity and Algorithms for Semipaired Domination in Graphs

OriginalPaper

Fixed-Parameter Tractability of (n − k) List Coloring

EditorialNotes

Editorial: Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019)

OriginalPaper

Parameterized Complexity of Min-Power Asymmetric Connectivity

Premium Partner

    Image Credits