Independence and domination in polygon graphs

DOI10.1016/0166-218X(93)90222-AzbMath0785.68072OpenAlexW1971604681MaRDI QIDQ686246

Ehab S. El-Mallah, Lorna K. Stewart

Publication date: 28 November 1993

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

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90222-a

zbMATH Keywords

minimum dominating setmaximum \(r\)-colorable subgraphpolygon graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Semitotal domination on AT-free graphs and circle graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Bichain graphs: geometric model and universal graphs ⋮ Parameterized domination in circle graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of domination problems in circle graphs
• Domination in permutation graphs
• The Complexity of Coloring Circular Arcs and Chords
• Recognizing circle graphs in polynomial time
• Algorithms for a maximum clique and a maximum independent set of a circle graph