\((p,k)\)-coloring problems in line graphs

DOI10.1016/j.tcs.2005.09.037zbMath1086.05029OpenAlexW2057777892MaRDI QIDQ817821

Dominique de Werra, Tınaz Ekim, Marc Demange

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.037

zbMATH Keywords

cocoloringsplit-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Fixed-parameter algorithms for the cocoloring problem ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ \((k,l)\)-colourings and Ferrers diagram representations of cographs ⋮ A tutorial on the use of graph coloring for some problems in robotics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On split-coloring problems
• A matching problem with side conditions
• On cocolourings and cochromatic numbers of graphs
• Partitioning chordal graphs into independent sets and cliques
• Approximating minimum cocolorings.
• Partitioning permutations into increasing and decreasing subsequences
• Partitioning cographs into cliques and stable sets
• Smallest-last ordering and clustering and graph coloring algorithms
• The NP-Completeness of Edge-Coloring
• Line perfect graphs
• List Partitions
• Node-and edge-deletion NP-complete problems
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• k-Components, Clusters and Slicings in Graphs

This page was built for publication: \((p,k)\)-coloring problems in line graphs