Partial Characterizations of Circular-Arc Graphs

DOI10.1016/J.ENDM.2008.01.009MaRDI QIDQ3503529zbMATH OpenOpenAlexFDO

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

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

circular-arc graphscographsdiamond-free graphspaw-free graphsclaw-free chordal

Mathematics Subject Classification ID

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

Recommendations

• Partial characterizations of circular-arc graphs
• Partial characterizations of circle graphs
• Circular‐arc digraphs: A characterization
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems

Cites work

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

Cited in

(22)

• scientific article; zbMATH DE number 1990726 (Why is no real title available?)
• The Branch-Width of Circular-Arc Graphs
• Proper circular arc graphs as intersection graphs of paths on a grid
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Boxicity of circular arc graphs
• Irredundancy in circular arc graphs
• Parity in knot theory
• Naji's characterization of circle graphs
• The restricted arc-width of a graph
• A note on the Hadwiger number of circular arc graphs
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Blocking quadruple: a new obstruction to circular-arc graphs
• Balancedness of subclasses of circular-arc graphs
• Partial characterizations of circle graphs
• Circular‐arc digraphs: A characterization
• Contact Graphs of Circular Arcs
• Partial characterizations of circular-arc graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Balancedness of some subclasses of circular-arc graphs
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Circular-arc hypergraphs: rigidity via connectedness
• Forbidden induced subgraph characterization of circle graphs within split graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503529)