On split-coloring problems

DOI10.1007/s10878-005-4103-7zbMath1122.05077OpenAlexW1970548872MaRDI QIDQ995923

Tınaz Ekim, Dominique de Werra

Publication date: 10 September 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://infoscience.epfl.ch/record/88644/files/10878_2005_Article_4103.pdf

zbMATH Keywords

partitioningpackingsplit-coloringvertex covering by split graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

Fixed-parameter algorithms for the cocoloring problem ⋮ Partitioning extended \(P_4\)-laden graphs into cliques and stable sets ⋮ A tutorial on the use of graph coloring for some problems in robotics ⋮ Vertex deletion problems on chordal graphs ⋮ Generalised online colouring problems in overlap graphs ⋮ Partitioning graphs into complete and empty graphs ⋮ Partitioning cographs into cliques and stable sets ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ \((p,k)\)-coloring problems in line graphs

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Split graphs of Dilworth number 2
• The splittance of a graph
• Split dimension of graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A hypocoloring model for batch scheduling
• Partitioning chordal graphs into independent sets and cliques
• Threshold graphs and related topics
• Incidence matrices and interval graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Depth-First Search and Linear Graph Algorithms