On the recognition of fuzzy circular interval graphs

Article, Preprint English OPEN
Oriolo , G.; Pietropaoli , Ugo; Stauffer , Gautier;
  • Publisher: Elsevier BV
  • Journal: Discrete Mathematics,volume 312,issue 8,pages1,426-1,435 (issn: 0012-365X)
  • Publisher copyright policies & self-archiving
  • Related identifiers: doi: 10.1016/j.disc.2011.12.029
  • Subject: Theoretical Computer Science | Computer Science - Discrete Mathematics | 68R10 | G.2.2 | Discrete Mathematics and Combinatorics
    arxiv: Computer Science::Discrete Mathematics | Mathematics::Combinatorics
    acm: MathematicsofComputing_DISCRETEMATHEMATICS

Fuzzy circular interval graphs are a generalization of proper circular arc graphs and have been recently introduced by Chudnovsky and Seymour as a fundamental subclass of claw-free graphs. In this paper, we provide a polynomial-time algorithm for recognizing such graphs... View more
  • References (13)
    13 references, page 1 of 2

    [1] Chen, L., “Efficient Parallel Recognition of Some Circular-Arc Graphs, II”. Algorithmica 17, 266-280, 1997.

    [2] Chudnovsky, M., and Seymour, P., “The Structure of Claw-free Graphs”. Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Series 327, 2005.

    [3] Chudnovsky, M., and Seymour, P., “Claw-free Graphs III: Circular Interval Graphs”. J. Combin. Theory Ser. B 98, 812- 834, 2008.

    [4] Chudnovsky, M., Private communication. ISMP 2006.

    [5] Corneil, D.G., Hiryoung, K., Natarajan, S., Olariu, S., and Sprague, A.P., “Simple linear time recognition of unit interval graphs”. Inform. Process. Lett. 55, 99-104, 1995.

    [6] Deng, X., Hell, P., and Huang, J., “Linear-time Representation Algorithms for Proper Circular-Arc Graphs and Prope r Interval Graphs”. SIAM J. Comput. 25, 390-403, 1996.

    [7] Eisenbrand, F., Oriolo, G., Stauffer, G., and Ventura, P., “The Stable Set Polytope of Quasi-line Graphs”. Combinatorica 28, 45-67, 2008. An extended abstract appeared in Proceedings of IPCO 2005.

    [8] Faenza, Y., Oriolo, G., and Snels, C., “Removing proper and homogeneous pairs of cliques while preserving some invariants”, manuscript.

    [9] Herrera de Figueiredo, C.M., Meidanis, J., and Picinin de Mello, C., “A linear-time algorithm for proper interval graph recognition”. Inform. Process. Lett. 56, 179-184, 1995.

    [10] King, A.D., and Reed, B.A., “Bounding χ in Terms of ω and Δ for Quasi-Line Graphs”. J. Graph Theory 59, 215-228, 2008.

  • Metrics
Share - Bookmark