\(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (Q747619): Difference between revisions

← Older edit

@@ aliases / en / 0 / aliases / en / 0 @@
+b-Coloring is NP-Hard on Co-Bipartite Graphs and Polytime Solvable on Tree-Cographs
@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 6495546
@@ Property / title @@
+b-Coloring is NP-Hard on Co-Bipartite Graphs and Polytime Solvable on Tree-Cographs (English)
+Normal rank
@@ Property / zbMATH Open document ID @@
+.05075
@@ Property / zbMATH Open document ID: 1451.05075 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/978-3-319-09174-7_9
@@ Property / DOI: 10.1007/978-3-319-09174-7_9 / rank @@
+Normal rank
@@ Property / author @@
+Flavia Bonomo-Braberman
@@ Property / author: Flavia Bonomo-Braberman / rank @@
+Normal rank
@@ Property / author @@
+Maya Jakobine Stein
@@ Property / author: Maya Jakobine Stein / rank @@
+Normal rank
@@ Property / published in @@
+Lecture Notes in Computer Science
@@ Property / published in: Lecture Notes in Computer Science / rank @@
+Normal rank
@@ Property / publication date @@
+October 2015Timestamp +2015-10-16T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2015-10-16T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 16 October 2015 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6495546
@@ Property / zbMATH DE Number: 6495546 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+\(b\)-chromatic number of graphs with stability number two
+Normal rank
@@ Property / zbMATH Keywords @@
+polynomial time dynamic programming algorithm
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3122637813
@@ Property / OpenAlex ID: W3122637813 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2104061284
@@ Property / OpenAlex ID: W2104061284 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.8313
@@ Property / arXiv ID: 1310.8313 / rank @@
+Normal rank
@@ Property / cites work @@
+TWO THEOREMS IN GRAPH THEORY
@@ Property / cites work: TWO THEOREMS IN GRAPH THEORY / rank @@
+Normal rank
@@ Property / cites work @@
+Achromatic number is NP-complete for cographs and interval graphs
+Normal rank
@@ Property / cites work @@
+On the b-coloring of cographs and \(P_{4}\)-sparse graphs
+Normal rank
@@ Property / cites work @@
+Discrete-Variable Extremum Problems
@@ Property / cites work: Discrete-Variable Extremum Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Paths, Trees, and Flowers
@@ Property / cites work: Paths, Trees, and Flowers / rank @@
+Normal rank
@@ Property / cites work @@
+The achromatic number of a graph
@@ Property / cites work: The achromatic number of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+\(b\)-coloring of tight graphs
@@ Property / cites work: \(b\)-coloring of tight graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the \(b\)-dominating coloring of graphs
@@ Property / cites work: On the \(b\)-dominating coloring of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On minimally \(b\)-imperfect graphs
@@ Property / cites work: On minimally \(b\)-imperfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The b-chromatic number of a graph
@@ Property / cites work: The b-chromatic number of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q4414507
@@ Property / cites work: Q4414507 / rank @@
+Normal rank
@@ Property / cites work @@
+Strong tree-cographs are Birkhoff graphs
@@ Property / cites work: Strong tree-cographs are Birkhoff graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Edge Dominating Sets in Graphs
@@ Property / cites work: Edge Dominating Sets in Graphs / rank @@
+Normal rank

Latest revision as of 22:43, 10 July 2024

scientific article; zbMATH DE number 6495546

b-Coloring is NP-Hard on Co-Bipartite Graphs and Polytime Solvable on Tree-Cographs

Language	Label	Description	Also known as
English	\(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs	scientific article; zbMATH DE number 6495546	b-Coloring is NP-Hard on Co-Bipartite Graphs and Polytime Solvable on Tree-Cographs