Structural parameterizations of b-coloring

DOI10.4230/LIPICS.ISAAC.2023.40MaRDI QIDQ6953177zbMATH OpenFDO

Authors Lars Jaffke, Paloma T. Lima, Roohani Sharma

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.40

zbMATH Keywords

\(b\)-coloringneighborhood diversitypathwidthstructural parameterizationtwin coverXNLP

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
• \(b\)-coloring of tight graphs
• A logic-based algorithmic meta-theorem for mim-width
• A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\)
• Algorithmic meta-theorems for restrictions of treewidth
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• Maximization coloring problems on graphs with few \(P_4\)
• On integer programming and convolution
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• On the Relationship Between Clique-Width and Treewidth
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parameterized Algorithms for Modular-Width
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Problems hard for treewidth but easy for stable gonality
• The \(b\)-chromatic index of graphs
• The b-chromatic number of a graph
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Twin-width. I: Tractable FO model checking
• XNLP-completeness for parameterized problems on graphs with a linear structure

Cited in

(1)

• Finding induced subgraphs from graphs with small mim-width

This page was built for publication: Structural parameterizations of \(b\)-coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953177)