On the recognition of fuzzy circular interval graphs

DOI10.1016/J.DISC.2011.12.029MaRDI QIDQ408180zbMATH OpenOpenAlexFDO

Authors Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer

Publication date 29 March 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.12.029

zbMATH Keywords

claw-free graphscircular interval graphshomogeneous cliques

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Fractional graph theory, fuzzy graph theory (05C72)

Recommendations

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Claw-free graphs. III: Circular interval graphs

Cites work

• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
• A linear time recognition algorithm for proper interval graphs
• A linear-time algorithm for proper interval graph recognition
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Claw-free graphs. III: Circular interval graphs
• Coloring fuzzy circular interval graphs
• Efficient parallel recognition of some circular arc graphs. II
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Maximum matching and a polyhedron with 0,1-vertices
• On maximal independent sets of vertices in claw-free graphs
• Paths, Trees, and Flowers
• Simple linear time recognition of unit interval graphs
• The stable set polytope of quasi-line graphs
• The structure of claw-free graphs

Cited in

(7)

• Solving the weighted stable set problem in claw-free graphs via decomposition
• Counting kernels in directed graphs with arbitrary orientations
• Graph classes and Ramsey numbers
• Coloring fuzzy circular interval graphs
• Coloring fuzzy circular interval graphs
• A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
• Parameterized complexity of induced graph matching on claw-free graphs

This page was built for publication: On the recognition of fuzzy circular interval graphs

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