Recognizing Berge graphs
From MaRDI portal
Publication:2494439
DOI10.1007/s00493-005-0012-8zbMath1089.05027OpenAlexW1991728994WikidataQ56388170 ScholiaQ56388170MaRDI QIDQ2494439
Xin-Ming Lu, Maria Chudnovsky, Kristina Vušković, P. D. Seymour, Cornuéjols, Gérard
Publication date: 27 June 2006
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-005-0012-8
Related Items
The computational complexity of the Edge-Perfect Graph and the Totally Balanced Packing Game recognition problems, Tractability in constraint satisfaction problems: a survey, Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, On coloring a class of claw-free graphs., On standard quadratic programs with exact and inexact doubly nonnegative relaxations, On the density of trigraph homomorphisms, NP-hardness of the recognition of coordinated graphs, Detecting 2-joins faster, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Detecting a long even hole, Even pairs in square-free Berge graphs, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Largest chordal and interval subgraphs faster than \(2^n\), Fixed interval scheduling: models, applications, computational complexity and algorithms, Triangulated neighborhoods in even-hole-free graphs, Clique-perfectness and balancedness of some graph classes, Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs, On bounding the difference between the maximum degree and the chromatic number by a constant, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, Associated primes of monomial ideals and odd holes in graphs, Forbidden induced subgraphs, On box-perfect graphs, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, On some graph classes related to perfect graphs: a survey, Complexity-separating graph classes for vertex, edge and total colouring, A coloring algorithm for \(4 K_1\)-free line graphs, Three-colourable perfect graphs without even pairs, Some problems on induced subgraphs, A linear time algorithm for the induced disjoint paths problem in planar graphs, Coloring vertices of a graph or finding a Meyniel obstruction, Line-graphs of cubic graphs are normal, Finding induced paths of given parity in claw-free graphs, Alternatives for testing total dual integrality, On claw-free \(t\)-perfect graphs, Automata for the verification of monadic second-order graph properties, Perfect graphs, kernels, and cores of cooperative games, Classes of perfect graphs, A Berge-keeping operation for graphs, On the forbidden induced subgraph sandwich problem, 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles, Hybrid tractability of valued constraint problems, Finding a smallest odd hole in a claw-free graph using global structure, Coloring square-free Berge graphs, Fair cost allocations under conflicts - a game-theoretic point of view -, Certifying algorithms, The three-in-a-tree problem, Algorithms for finding an induced cycle in planar graphs, The complexity of recognizing linear systems with certain integrality properties, Practical and efficient split decomposition via graph-labelled trees, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Polynomial cases for the vertex coloring problem, Coloring perfect graphs with no balanced skew-partitions, Recognition of unipolar and generalised split graphs, A new characterization of HH-free graphs, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, Decomposing Berge graphs and detecting balanced skew partitions, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, On the complexity of 4-coloring graphs without long induced paths, Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture, Two complexity results for the vertex coloring problem, Strict chordal and strict split digraphs, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, On the mixed set covering, packing and partitioning polytope, A polynomial Turing-kernel for weighted independent set in bull-free graphs, An SDP primal-dual algorithm for approximating the Lovász-theta function, On the barrier graph of an arrangement of ray sensors, Transitive orientations in bull-reducible Berge graphs, The external constraint 4 nonempty part sandwich problem, On Roussel-Rubio-type lemmas and their consequences, The P versus NP-complete dichotomy of some challenging problems in graph theory, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Finding induced trees, A polyhedral approach to the stability of a family of coalitions, Polyhedral properties of the induced cluster subgraphs, NP-completeness results for edge modification problems, On a connection between facility location and perfect graphs, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Approximability of clique transversal in perfect graphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Detecting a long odd hole, Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable, The sandwich problem for decompositions and almost monotone properties, Perfectness of clustered graphs, Parameterizing above or below guaranteed values, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, Partial characterizations of coordinated graphs: Line graphs and complements of forests, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, Combinatorial optimization with 2-joins, The structure of bull-free graphs I -- three-edge-paths with centers and anticenters, Vertex- and edge-minimal and locally minimal graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Miscellaneous Digraph Classes, The Structure of Bull-Free Perfect Graphs, On coloring a class of claw-free and hole-twin-free graphs, On the properties of weighted minimum colouring games, Recognizing balanceable matrices, Universally balanced combinatorial optimization games, A faster algorithm to recognize even-hole-free graphs, Point partition numbers: perfect graphs, Finding a shortest even hole in polynomial time, Optimizing concurrency under Scheduling by Edge Reversal, The Induced Disjoint Paths Problem, Coloring \((4K_1,C_4,C_6)\)-free graphs, Graphs of large chromatic number, Easily Testable Graph Properties, Hybrid Tractable Classes of Constraint Problems, The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, Odd Holes in Bull-Free Graphs, Detecting induced subgraphs, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, A tutorial on branch and cut algorithms for the maximum stable set problem, A structure theorem for graphs with no cycle with a unique chord and its consequences, The perfection and recognition of bull-reducible Berge graphs, On minimal forbidden subgraph characterizations of balanced graphs, Algorithmic bounds for the chromatic number†, Clique-perfectness of complements of line graphs, On minimal forbidden subgraph characterizations of balanced graphs, Complexity of clique-coloring odd-hole-free graphs, Counting Weighted Independent Sets beyond the Permanent, Perfect Digraphs, On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five, Unnamed Item, Algorithms for 3PC(⋅, ⋅)-free Berge graphs, Characterization and recognition of Helly circular-arc clique-perfect graphs
