On the minimum and maximum selective graph coloring problems in some graph classes

DOI10.1016/j.dam.2015.10.005zbMath1333.05106OpenAlexW1960344525MaRDI QIDQ266810

Marc Demange, Bernard Ries, Tınaz Ekim

Publication date: 7 April 2016

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

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

zbMATH Keywords

complexityapproximationgraph classes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items

On some applications of the selective graph coloring problem, An exact algorithm for the partition coloring problem, Uncertain vertex coloring problem, A note on selective line-graphs and partition colorings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Routing and wavelength assignment by partition colouring
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• Perfectness of clustered graphs
• Claw-free graphs. VII. Quasi-line graphs
• A branch-and-price approach for the partition coloring problem
• On the complexity of the selective graph coloring problem in some special classes of graphs
• On some applications of the selective graph coloring problem
• A branch-and-cut algorithm for partition coloring
• The Complexity of Coloring Circular Arcs and Chords
• The Complexity of Multiterminal Cuts
• The complexity of path coloring and call scheduling