\(b\)-coloring parameterized by clique-width
From MaRDI portal
Publication:6614620
DOI10.1007/s00224-023-10132-0zbMath1548.05127MaRDI QIDQ6614620
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
Publication date: 7 October 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs
- On the parameterized complexity of b-\textsc{chromatic number}
- Fundamentals of parameterized complexity
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- The behavior of clique-width under graph operations and graph transformations
- On the \(b\)-coloring of \(P_{4}\)-tidy graphs
- Improved upper bounds for vertex cover
- \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
- Clique-width of graphs defined by one-vertex extensions
- Fall colouring of bipartite graphs and Cartesian products of graphs
- On the b-coloring of cographs and \(P_{4}\)-sparse graphs
- Distance-hereditary graphs
- The b-chromatic number of a graph
- \(k\)-NLC graphs and polynomial algorithms
- Treewidth. Computations and approximations
- Clique-width of partner-limited graphs
- Which problems have strongly exponential complexity?
- Edge-\(b\)-coloring trees
- Graphs with small fall-spectrum
- \(b\)-coloring of tight graphs
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Independent domination in graphs: A survey and recent results
- On the Grundy and \(b\)-chromatic numbers of a graph
- Upper bounds to the clique width of graphs
- A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
- Graphs of girth at least 7 have high \(b\)-chromatic number
- The \(b\)-chromatic index of graphs
- Handle-rewriting hypergraph grammars
- Maximization coloring problems on graphs with few \(P_4\)
- Intractability of Clique-Width Parameterizations
- About the b-continuity of graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Approximation results for the optimum cost chromatic partition problem
- Clique-width III
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Finer Tight Bounds for Coloring on Clique-Width
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Parameterized Algorithms
- Slightly Superexponential Parameterized Problems
- Complexity of fall coloring for restricted graph classes
- On the complexity of \(k\)-SAT
This page was built for publication: \(b\)-coloring parameterized by clique-width
