Top

Published in:

2013 | OriginalPaper | Chapter

Beyond Perfection: Computational Results for Superclasses

Authors : Arnaud Pêcher, Annegret K. Wagler

Published in: Facets of Combinatorial Optimization

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We arrived at the Zuse Institute Berlin, Annegret as doctoral student in 1995 and Arnaud as postdoc in 2001, both being already fascinated from the graph theoretical properties of perfect graphs. Through encouraging discussions with Martin, we learned about the manifold links of perfect graphs to other mathematical disciplines and the resulting algorithmic properties based on the theta number (where Martin got famous for, together with Laci Lovász and Lex Schrijver).

This made us wonder whether perfect graphs are indeed completely unique and exceptional, or whether some of the properties and concepts can be generalized to larger graph classes, with similar algorithmic consequences—the starting point of a fruitful collaboration. Here, we answer this question affirmatively and report on the recently achieved results for some superclasses of perfect graphs, all relying on the polynomial time computability of the theta number. Finally, we give some reasons that the theta number plays a unique role in this context.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Mirror-Descent Methods in Mixed-Integer Convex Optimization

next chapter From Vertex-Telecenters to Subtree-Telecenters

Bachoc, C., Pêcher, A., Thiery, A.: On the theta number of powers of cycle graphs. Combinatorica (to appear)

Bang-Jensen, J., Huang, J.: Convex-round graphs are circular-perfect. J. Graph Theory 40, 182–184 (2002) MathSciNetMATHCrossRef

Berge, C.: Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe 10, 114–115 (1961)

Bondy, J., Hell, P.: A note on the star chromatic number. J. Graph Theory 14, 479–482 (1990) MathSciNetMATHCrossRef

Brimkov, V., Codenotti, B., Crespi, V., Leoncini, M.: On the Lovász number of certain circular graphs. Lect. Notes Comput. Sci. 1767, 291–305 (2000) MathSciNetCrossRef

Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006) MathSciNetMATHCrossRef

Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Ser. B 18, 138–154 (1975) MATHCrossRef

Coulonges, S., Pêcher, A., Wagler, A.: Characterizing and bounding the imperfection ratio for some classes of graphs. Math. Program., Ser. A 118, 37–46 (2009) MATHCrossRef

Deuber, W., Zhu, X.: Circular coloring of weighted graphs. J. Graph Theory 23, 365–376 (1996) MathSciNetMATHCrossRef

10.

Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an O(n ³)-algorithm for the weighted stable set problem. In: Proceedings of SODA, pp. 630–646 (2011)

11.

Fulkerson, D.: Blocking and antiblocking pairs of polyhedra. Math. Program. 1, 168–194 (1971) MathSciNetMATHCrossRef

12.

Fulkerson, D.: Anti-blocking polyhedra. J. Comb. Theory, Ser. B 12, 50–71 (1972) MathSciNetMATHCrossRef

13.

Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976) MathSciNetMATHCrossRef

14.

Grötschel, M.: My favorite theorem: characterizations of perfect graphs. Optima 62, 2–5 (1999)

15.

Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981) MathSciNetMATHCrossRef

16.

Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Topics on Perfect Graphs. North-Holland Math. Stud., vol. 88, pp. 325–356 (1984) CrossRef

17.

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988) MATHCrossRef

18.

Holyer, I.: The NP-completeness of edge-colouring. SIAM J. Comput. 10, 718–720 (1981) MathSciNetMATHCrossRef

19.

Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45, 246–265 (1998) MathSciNetMATHCrossRef

20.

Kuhpfahl, J., Wagler, A., Wagner, C.: Circular-imperfection of triangle free graphs. Electron. Notes Discrete Math. 29, 163–167 (2007) CrossRef

21.

Kuratowski, K.: Sur le problème des courbes gauches en topologie. Fundam. Math. 15, 271–283 (1930) MATH

22.

Lovász, L.: A characterization of perfect graphs. J. Comb. Theory, Ser. B 13, 95–98 (1972) MATHCrossRef

23.

Lovász, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267 (1972) MathSciNetMATHCrossRef

24.

Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1–7 (1979) MATHCrossRef

25.

Oriolo, G., Stauffer, G., Ventura, P.: Stable sets in claw-free graphs: recent achievements and future challenges. Optima 86, 2–5 (2011)

26.

Padberg, M.: Perfect zero-one matrices. Math. Program. 6, 180–196 (1974) MathSciNetMATHCrossRef

27.

Pêcher, A., Wagler, A.: Almost all webs are not rank-perfect. Math. Program., Ser. B 105(2–3), 311–328 (2006) MATHCrossRef

28.

Pêcher, A., Wagler, A.: On classes of minimal circular-imperfect graphs. Discrete Appl. Math. 156, 998–1010 (2008) MathSciNetMATHCrossRef

29.

Pêcher, A., Wagler, A.: On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs. Electron. Notes Discrete Math. 35, 53–58 (2009) CrossRef

30.

Pêcher, A., Wagler, A.: Clique and chromatic number of circular-perfect graphs. Electron. Notes Discrete Math. 36, 199–206 (2010) CrossRef

31.

Pêcher, A., Wagler, A.: Computing the clique number of a-perfect graphs in polynomial time. Electron. Notes Discrete Math. 38, 705–710 (2011) CrossRef

32.

Pêcher, A., Wagler, A.: Computing clique and chromatic number of circular-perfect graphs in polynomial time. Math. Program., Ser. A (2012). doi:10.1007/s10107-012-0512-4

33.

Pêcher, A., Wagler, A.: Computing the clique number of a-perfect graphs in polynomial time. Eur. J. Comb. (to appear)

34.

Pêcher, A., Zhu, X.: Claw-free circular-perfect graphs. J. Graph Theory 65, 163–172 (2010) MathSciNetMATHCrossRef

35.

Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: The four colour theorem. J. Comb. Theory, Ser. B 70, 2–44 (1997) MathSciNetMATHCrossRef

36.

Shannon, C.E.: The zero-error capacity of a noisy channel. IRE Trans. Inf. Theory 2, 8–19 (1956) MathSciNetCrossRef

37.

Shepherd, F.B.: Applying Lehman’s theorem to packing problems. Math. Program. 71, 353–367 (1995) MathSciNetMATH

38.

Szegedy, M.: A note on the number of Lovász and the generalized Delsarte bound. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 36–39 (1994) CrossRef

39.

Trotter, L.E. Jr.: A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12, 373–388 (1975) MathSciNetMATHCrossRef

40.

Vince, A.: Star chromatic number. J. Graph Theory 12, 551–559 (1988) MathSciNetMATHCrossRef

41.

Vizing, V.: Vertex colorings with given colors. Diskretn. Anal. 29, 3–10 (1976) (in Russian) MathSciNetMATH

42.

Wagler, A.: Rank-perfect and weakly rank-perfect graphs. Math. Methods Oper. Res. 95, 127–149 (2002) MathSciNet

43.

Wagler, A.: Antiwebs are rank-perfect. 4OR 2, 149–152 (2004) MathSciNetMATHCrossRef

44.

Wagler, A.: On rank-perfect subclasses of near-bipartite graphs. 4OR 3, 329–336 (2005) MathSciNetMATHCrossRef

45.

Xu, Y.: Minimally circular-imperfect graphs with a major vertex. Discrete Math. 301, 239–242 (2005) MathSciNetMATHCrossRef

46.

Zhu, X.: Circular perfect graphs. J. Graph Theory 48(1–3), 186–209 (2005) MathSciNetMATHCrossRef

Title: Beyond Perfection: Computational Results for Superclasses
Authors: Arnaud Pêcher
Annegret K. Wagler
Publisher: Springer Berlin Heidelberg
Book: Facets of Combinatorial Optimization
Print ISBN: 978-3-642-38188-1

Electronic ISBN: 978-3-642-38189-8

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-3-642-38189-8_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"