Recognizing Berge graphs
From MaRDI portal
Publication:2494439
Recommendations
Cited in
(only showing first 100 items - show all)- Complexity-separating graph classes for vertex, edge and total colouring
- On coloring a class of claw-free graphs.
- On the properties of weighted minimum colouring games
- Coloring \((4K_1,C_4,C_6)\)-free graphs
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
- Recognizing balanceable matrices
- On some graph classes related to perfect graphs: a survey
- Detecting a long even hole
- A Berge-keeping operation for graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- Some problems on induced subgraphs
- Point partition numbers: perfect graphs
- On box-perfect graphs
- On the density of trigraph homomorphisms
- Detecting a long odd hole
- Finding a smallest odd hole in a claw-free graph using global structure
- Miscellaneous digraph classes
- Alternatives for testing total dual integrality
- On bounding the difference between the maximum degree and the chromatic number by a constant
- Characterization and recognition of Helly circular-arc clique-perfect graphs
- Hybrid tractable classes of constraint problems
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Clique-perfectness and balancedness of some graph classes
- scientific article; zbMATH DE number 1445285 (Why is no real title available?)
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- Finding a shortest even hole in polynomial time
- Polyhedral properties of the induced cluster subgraphs
- A new characterization of HH-free graphs
- An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Universally balanced combinatorial optimization games
- Odd holes in bull-free graphs
- The structure of bull-free perfect graphs
- A faster algorithm to recognize even-hole-free graphs
- Approximability of clique transversal in perfect graphs
- Triangulated neighborhoods in even-hole-free graphs
- Easily testable graph properties
- A faster algorithm to recognize even-hole-free graphs
- A coloring algorithm for \(4 K_1\)-free line graphs
- Forbidden induced subgraphs
- Algorithmic bounds for the chromatic number†
- On a connection between facility location and perfect graphs
- An SDP primal-dual algorithm for approximating the Lovász-theta function
- Classes of perfect graphs
- On the mixed set covering, packing and partitioning polytope
- NP-hardness of the recognition of coordinated graphs
- On coloring a class of claw-free and hole-twin-free graphs
- On the forbidden induced subgraph sandwich problem
- Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
- Recognition of unipolar and generalised split graphs
- Practical and efficient split decomposition via graph-labelled trees
- Certifying algorithms
- Tractability in constraint satisfaction problems: a survey
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Finding induced trees
- Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- The external constraint 4 nonempty part sandwich problem
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- On the maximum weight independent set problem in graphs without induced cycles of length at least five
- Automata for the verification of monadic second-order graph properties
- The Induced Disjoint Paths Problem
- A tutorial on branch and cut algorithms for the maximum stable set problem
- Perfect graphs, kernels, and cores of cooperative games
- Fair cost allocations under conflicts - a game-theoretic point of view -
- Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
- Coloring vertices of a graph or finding a Meyniel obstruction
- The three-in-a-tree problem
- On the complexity of 4-coloring graphs without long induced paths
- Three-colourable perfect graphs without even pairs
- A polyhedral approach to the stability of a family of coalitions
- The complexity of recognizing linear systems with certain integrality properties
- Clique-perfectness of complements of line graphs
- Perfect digraphs
- An efficient partitioning oracle for bounded-treewidth graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- The perfection and recognition of bull-reducible Berge graphs
- Polynomial cases for the vertex coloring problem
- Decomposing Berge graphs and detecting balanced skew partitions
- NP-completeness results for edge modification problems
- Detecting 2-joins faster
- On claw-free \(t\)-perfect graphs
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
- Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
- Vertex- and edge-minimal and locally minimal graphs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Coloring square-free Berge graphs
- Associated primes of monomial ideals and odd holes in graphs
- Coloring perfect graphs with no balanced skew-partitions
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- Perfect graphs with no balanced skew-partition are 2-clique-colorable
- Recognizing Cartesian graph bundles
This page was built for publication: Recognizing Berge graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494439)
