On the structure of certain intersection graphs

DOI10.1016/J.IPL.2006.01.013MaRDI QIDQ845675zbMATH OpenOpenAlexFDO

Authors Kathie Cameron, Chính T. Hoàng

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.01.013

zbMATH Keywords

computational geometrychromatic numberintersection graphsperfect graphpolygon-circle graphgraph divisibilityinterval-filament graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Recommendations

• 3D-interval-filament graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Covering and coloring polygon-circle graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs

Cites work

• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 1439504 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• An Efficient Test for Circular-Arc Graphs
• Coloring a Family of Circular Arcs
• Comparability graphs and intersection graphs
• Covering and coloring polygon-circle graphs
• Graph Classes: A Survey
• Linear-time recognition of circular-arc graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• On the divisibility of graphs
• Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
• Recognizing circle graphs in polynomial time
• Star-cutsets and perfect graphs
• The strong perfect graph theorem
• Thresholds for classes of intersection graphs

Cited in

(23)

• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• Ordered graphs and large bi-cliques in intersection graphs of curves
• scientific article; zbMATH DE number 5777931 (Why is no real title available?)
• Finding intersection models: from chordal to Helly circular-arc graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• scientific article; zbMATH DE number 2084282 (Why is no real title available?)
• A characterization of the odd graphs and the doubled odd graphs with a few of their intersection numbers
• Intersection graphs of homothetic polygons
• scientific article; zbMATH DE number 4134102 (Why is no real title available?)
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Tractabilities and intractabilities on geometric intersection graphs
• Modular intersection graphs
• A generalization of line graphs: (X, Y)-intersection graphs
• Stable 2-pairs and (X,Y)-intersection graphs
• Intersections of largest bonds in \(k\)-connected graphs
• Characterizing intersection classes of graphs
• On grid intersection graphs
• scientific article; zbMATH DE number 2100931 (Why is no real title available?)
• scientific article; zbMATH DE number 7071225 (Why is no real title available?)
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• 3D-interval-filament graphs
• On the intersection graphs associeted to posets
• Refining the hierarchies of classes of geometric intersection graphs

This page was built for publication: On the structure of certain intersection graphs

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