Fixed-parameter algorithms for the cocoloring problem

DOI10.1016/j.dam.2013.11.010zbMath1284.05093OpenAlexW2018100548MaRDI QIDQ2440099

Yanyan Li

Publication date: 27 March 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.11.010

zbMATH Keywords

fixed-parameter tractabilitybounded treewidth\((q,q-4)\)-graphscocoloringcochromatic number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Spy game: FPT-algorithm, hardness and graph products ⋮ Spy game: FPT-algorithm and results on graph products ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Some of My Favorite Coloring Problems for Graphs and Digraphs ⋮ Fractional cocoloring of graphs

Cites Work

• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Graph minors. III. Planar tree-width
• \((p,k)\)-coloring problems in line graphs
• On split-coloring problems
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• On the structure of graphs with few \(P_4\)s
• Partitioning chordal graphs into independent sets and cliques
• Approximating minimum cocolorings.
• Partitions of graphs into one or two independent sets and cliques
• Matrix partitions of perfect graphs
• Partitioning cographs into cliques and stable sets
• Chromatic number versus chromatic number in graphs with bounded clique number
• Complexity of graph partition problems
• Characterizing –partitionable Cographs
• Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
• A Linear Recognition Algorithm for Cographs
• Some extremal results in cochromatic and dichromatic theory
• List Partitions
• On the approximation of Min Split-coloring and Min Cocoloring
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Efficient algorithms for graphs with few \(P_4\)'s
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item