On cocolourings and cochromatic numbers of graphs

DOI10.1016/0166-218X(92)00121-2zbMath0795.05052MaRDI QIDQ1315460

Dieter Kratsch, Lorna K. Stewart, John G. Gimbel

Publication date: 29 August 1994

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

zbMATH Keywords

chordal graphsNP-completepolynomial time algorithmsline graphscomparability graphscochromatic numbercochromatic number problemcocolouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

The complexity of generalized graph colorings ⋮ Partitions of graphs into cographs ⋮ Some defective parameters in graphs ⋮ \((k,l)\)-colourings and Ferrers diagram representations of cographs ⋮ A tutorial on the use of graph coloring for some problems in robotics ⋮ On the complexity of generalized chromatic polynomials ⋮ Advances on defective parameters in graphs ⋮ Unnamed Item ⋮ Partitioning graphs into complete and empty graphs ⋮ Partitioning cographs into cliques and stable sets ⋮ Approximating minimum cocolorings. ⋮ \((p,k)\)-coloring problems in line graphs

Cites Work

• Clustering and domination in perfect graphs
• Some topics in cochromatic theory
• Complement reducible graphs
• NP-completeness of edge-colouring some restricted graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Chromatic number versus chromatic number in graphs with bounded clique number
• A Linear Recognition Algorithm for Cographs
• The NP-completeness column: an ongoing guide
• Algorithmic Aspects of Vertex Elimination on Graphs
• Cochromatic Number and the Genus of a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On cocolourings and cochromatic numbers of graphs