Partial Characterizations of Circular-Arc Graphs

DOI10.1016/j.endm.2008.01.009zbMath1341.05164OpenAlexW1986795429MaRDI QIDQ3503529

Luciano N. Grippo, Guillermo Durán, Martín D. Safe, Flavia Bonomo-Braberman

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/140829

zbMATH Keywords

cographsdiamond-free graphscircular-arc graphspaw-free graphsclaw-free chordal

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Characterizations and recognition of circular-arc graphs and subclasses: a survey

Cites Work

• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• On chordal proper circular arc graphs
• Linear-time recognition of circular-arc graphs
• Structure theorems for some circular-arc graphs
• Representation of a finite graph by a set of intervals on the real line
• Efficient construction of unit circular-arc models
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Polynomial time recognition of unit circular-arc graphs

This page was built for publication: Partial Characterizations of Circular-Arc Graphs