The strong perfect graph theorem
From MaRDI portal
Publication:855256
DOI10.4007/annals.2006.164.51zbMath1112.05042arXivmath/0212070OpenAlexW1973199140WikidataQ29028413 ScholiaQ29028413MaRDI QIDQ855256
Maria Chudnovsky, P. D. Seymour, Robin Thomas, Neil Robertson
Publication date: 4 January 2007
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0212070
Related Items
Clique-stable set separation in perfect graphs with no balanced skew-partitions, Tractability in constraint satisfaction problems: a survey, Graphs with induced-saturation number zero, Chromatic number of \(P_5\)-free graphs: Reed's conjecture, An extension of Lehman's theorem and ideal set functions, Induced cycles in triangle graphs, Exploring the concept of perfection in 3-hypergraphs, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, Even pairs in square-free Berge graphs, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Star chromatic bounds, Largest chordal and interval subgraphs faster than \(2^n\), Simple and three-valued simple minimum coloring games, Complexity of coloring graphs without paths and cycles, Characterization and recognition of some opposition and coalition graph classes, Colouring perfect graphs with bounded clique number, Rainbow generalizations of Ramsey theory: A survey, Polytopes of minimum positive semidefinite rank, Fast recognition of doubled graphs, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Associated primes of monomial ideals and odd holes in graphs, A supernodal formulation of vertex colouring with applications in course timetabling, Parameterized complexity of vertex deletion into perfect graph classes, Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, On a graph of monogenic semigroups, On the independence numbers of the cubes of odd cycles, Graph classes and Ramsey numbers, Finding clubs in graph classes, On a conjecture concerning the Petersen graph. II, Random threshold digraphs, Claw-free graphs with strongly perfect complements. Fractional and integral version. I: Basic graphs, Claw-free graphs with strongly perfect complements. Fractional and integral version. II: Nontrivial strip-structures, Three-colourable perfect graphs without even pairs, Classes of graphs with small rank decompositions are \(\chi \)-bounded, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Some properties of graphs determined by edge zeta functions, A linear time algorithm for the induced disjoint paths problem in planar graphs, Graphs of separability at most 2, Well-covered circulant graphs, Coloring vertices of a graph or finding a Meyniel obstruction, On claw-free \(t\)-perfect graphs, A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants), A new characterization of perfect graphs, On graphs with no induced subdivision of \(K_4\), Total chromatic number of unichord-free graphs, Colouring, constraint satisfaction, and complexity, Substitution and \(\chi\)-boundedness, On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes, Regular inference as vertex coloring, Certifying algorithms, Algorithms for finding an induced cycle in planar graphs, Vertex-transitive CIS graphs, Practical and efficient split decomposition via graph-labelled trees, Some properties of edge intersection graphs of single-bend paths on a grid, Excluding cycles with a fixed number of chords, Coloring graphs characterized by a forbidden subgraph, Minimal classes of graphs of unbounded clique-width, Path-bicolorable graphs, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Handelman's hierarchy for the maximum stable set problem, On circulant thin Lehman matrices, Polynomial cases for the vertex coloring problem, Coloring perfect graphs with no balanced skew-partitions, Total domination edge critical graphs with total domination number three and many dominating pairs, Non-minimal degree-sequence-forcing triples, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, On bounding the difference of the maximum degree and the clique number, Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, On the choosability of claw-free perfect graphs, Clique-perfectness of claw-free planar graphs, Two complexity results for the vertex coloring problem, Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors, Perfect zero-divisor graphs, On the chromatic number of \((P_{5},K_{2,t})\)-free graphs, Strict chordal and strict split digraphs, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, Critical hereditary graph classes: a survey, Excluding paths and antipaths, A polynomial Turing-kernel for weighted independent set in bull-free graphs, Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs, On the barrier graph of an arrangement of ray sensors, Perfect commuting graphs, Transitive orientations in bull-reducible Berge graphs, The external constraint 4 nonempty part sandwich problem, On Roussel-Rubio-type lemmas and their consequences, Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs, Lower bounds for kernelizations and other preprocessing procedures, Injective colorings of graphs with low average degree, Boundary properties of graphs for algorithmic graph problems, Some remarks on Hajós' conjecture, Some new hereditary classes where graph coloring remains NP-hard, Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs, Maximum weight independent sets in hole- and dart-free graphs, An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs, Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals, Perfect graphs involving semitotal and semipaired domination, Definability in the substructure ordering of simple graphs, On the independence polynomial of the corona of graphs, A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs, A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs, Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors, THE CHROMATIC NUMBER OF -FREE GRAPHS, Triangle‐free graphs with large chromatic number and no induced wheel, Some Recent Results on the Graphs of Finite-Dimensional Vector Spaces, Minimum weighted clique cover on claw‐free perfect graphs, Coloring rings, On graphs with no induced five‐vertex path or paraglider, Finding a shortest even hole in polynomial time, Coloring of some crown-free graphs, Chordal and perfect zero-divisor graphs of posets and applications to graphs associated with algebraic structures, Induced odd cycle packing number, independent sets, and chromatic number, Attempting perfect hypergraphs, Strongly perfect claw‐free graphs—A short proof, An optimal χ‐bound for (P6, diamond)‐free graphs, (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels, Polynomial bounds for chromatic number VII. Disjoint holes, On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques, A Sum of Squares Characterization of Perfect Graphs, The complement of the intersection graph of ideals of a poset, Coloring \((4K_1,C_4,C_6)\)-free graphs, Perfectly contractile graphs and quadratic toric rings, Interview with Gil Kalai, Interview with Karim Adiprasito, Complement of the reduced non-zero component graph of free semimodules, Chromatic bounds for some subclasses of \((P_3\cup P_2)\)-free graphs, On \(\chi \)-diperfect digraphs with stability number two, On chromatic number and perfectness of fuzzy graph, Ramsey numbers and graph parameters, Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs, Divisibility and coloring of some \(P_5\)-free graphs, On CD-chromatic number and its lower bound in some classes of graphs, Star covers and star partitions of double-split graphs, On the chromatic number of (P5,dart)-free graphs, Perfectness of \(G\)-generalized join of graphs, Coloring graphs with no induced five‐vertex path or gem, 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs, Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors, Strengthening Brooks' chromatic bound on \(P_6\)-free graphs, Burling graphs revisited. II: Structure, Critical (\(P_5\), bull)-free graphs, Some results on \(k\)-critical \(P_5\)-free graphs, On minimally non-firm binary matrices, Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs, Towards the Chen-Raspaud conjecture, Coloring (\(P_5\), kite)-free graphs with small cliques, Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs, Near optimal colourability on hereditary graph families, Graphs of large chromatic number, Unnamed Item, Vertex deletion into bipartite permutation graphs, Comparing Imperfection Ratio and Imperfection Index for Graph Classes, Vizing bound for the chromatic number on some graph classes, Reconfiguration of colorable sets in classes of perfect graphs, Reflexive polytopes arising from partially ordered sets and perfect graphs, Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3, The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs, Excluding Induced Subdivisions of the Bull and Related Graphs, A Characterization of b-Perfect Graphs, The A4-structure of a graph, Perfect Graphs of Fixed Density: Counting and Homogeneous Sets, Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement, Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, Clique-perfectness and balancedness of some graph classes, Perfect graphs for domination games, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs, Counting List Matrix Partitions of Graphs, Triangle packings and transversals of some \(K_{4}\)-free graphs, On the chromatic number of (\(P_6\), diamond)-free graphs, Complementation in T-perfect graphs, Local 2-separators, Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs, Decomposing and colouring some locally semicomplete digraphs, Structural Investigation of Piecewise Linearized Network Flow Problems, On \(r\)-hued colorings of graphs without short induced paths, Amalgams and χ-Boundedness, Bounding clique-width via perfect graphs, Line-graphs of cubic graphs are normal, Forbidden lifts (NP and CSP for combinatorialists), On tension-continuous mappings, Minimal circular-imperfect graphs of large clique number and large independence number, Finding induced paths of given parity in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs, Alternatives for testing total dual integrality, FPT and kernelization algorithms for the induced tree problem, Graph theory. Abstracts from the workshop held January 2--8, 2022, Extended skew partition problem, Berge's conjecture on directed path partitions -- a survey, Classes of perfect graphs, Grinstead's conjecture is true for graphs with a small clique number, A Berge-keeping operation for graphs, Characterizing N+-perfect line graphs, On the probe problem for \((r,\ell )\)-well-coveredness, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Exact and Parameterized Algorithms for (k, i)-Coloring, A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs, The Turán number of directed paths and oriented cycles, Graphs with No Induced Five‐Vertex Path or Antipath, 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles, Forbidden graphs for classes of split-like graphs, On opposition graphs, coalition graphs, and bipartite permutation graphs, Boundary graph classes for some maximum induced subgraph problems, Forbidden subgraphs and the König-Egerváry property, Finding a smallest odd hole in a claw-free graph using global structure, A note on the Cornaz-Jost transformation to solve the graph coloring problem, 2-clique-bond of stable set polyhedra, The linear guessing number of undirected graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Some classes of perfect strongly annihilating-ideal graphs associated with commutative rings, GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS, Shortest Paths between Shortest Paths and Independent Sets, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, On the Chvátal rank of linear relaxations of the stable set polytope, Solution of three problems of Cornuéjols, Decomposing Berge graphs and detecting balanced skew partitions, NP-hard graph problems and boundary classes of graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, On the complexity of 4-coloring graphs without long induced paths, Combinatorial symbolic powers, On classes of minimal circular-imperfect graphs, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Skew partitions in perfect graphs, Unnamed Item, On extracting maximum stable sets in perfect graphs using Lovász's theta function, On the existence of \((k,l)\)-kernels in infinite digraphs: a survey, Bounding Clique-Width via Perfect Graphs, Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable, Vertex elimination orderings for hereditary graph classes, Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, Graph minor theory, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Open Problems on Graph Coloring for Special Graph Classes, Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time, Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, Monomial Cut Ideals, Skew partition sandwich problem is NP-complete, On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs, Miscellaneous Digraph Classes, Perfect circular arc coloring, Characterising claw-free t-perfect graphs, The Structure of Bull-Free Perfect Graphs, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, A class of perfectly contractile graphs, Minimally circular-imperfect graphs with a major vertex, Almost all webs are not rank-perfect, Algorithms for 3PC(⋅, ⋅)-free Berge graphs, The Erdös-Hajnal Conjecture-A Survey, Independent domination in hereditary classes, Chordless paths through three vertices, On cd-coloring of trees and co-bipartite graphs, Stable skew partition problem, Chordal probe graphs, NP-hardness of the recognition of coordinated graphs, On the chromatic number of \(2 K_2\)-free graphs, Mock threshold graphs, On the structure of certain intersection graphs, On independent vertex sets in subclasses of apple-free graphs, A construction for non-rank facets of stable set polytopes of webs, Fixed interval scheduling: models, applications, computational complexity and algorithms, A bipartite analogue of Dilworth's theorem, Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes, Triangulated neighborhoods in even-hole-free graphs, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, A note on chromatic number and induced odd cycles, MSOL partitioning problems on graphs of bounded treewidth and clique-width, On box-perfect graphs, On the forbidden induced subgraph probe and sandwich problems, A coloring algorithm for \(4 K_1\)-free line graphs, Chromatic number and subtrees of graphs, Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs, A class of perfect graphs containing \(P_{6}\), Colouring of \((P_3 \cup P_2)\)-free graphs, Star coloring of certain graph classes, The normal graph conjecture for two classes of sparse graphs, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs, Characterization of forbidden subgraphs for bounded star chromatic number, A note on chromatic number of (cap, even hole)-free graphs, Coloring square-free Berge graphs, Square-free perfect graphs., 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs., Fair cost allocations under conflicts - a game-theoretic point of view -, The complexity of recognizing linear systems with certain integrality properties, On minimally circular-imperfect graphs, Critical \((P_6, \mathrm{banner})\)-free graphs, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Sum-perfect graphs, Problems and results in extremal combinatorics. II, Claw-free graphs. IV: Decomposition theorem, Solving some NP-complete problems using split decomposition, Reflexive polytopes arising from perfect graphs, Even pairs and prism corners in square-free Berge graphs, Polyhedral studies of vertex coloring problems: the standard formulation, On the mixed set covering, packing and partitioning polytope, Finding balance: split graphs and related classes, The Erdős-Hajnal conjecture for bull-free graphs, Extremal colorings and independent sets, \(2K_2\)-partition of some classes of graphs, The P versus NP-complete dichotomy of some challenging problems in graph theory, \(K_{4}\)-free graphs with no odd holes, \(2K_{2}\) vertex-set partition into nonempty parts, Induced disjoint paths problem in a planar digraph, On cover-structure graphs, A note on kernels and Sperner's Lemma, A polyhedral approach to the stability of a family of coalitions, A magnetic procedure for the stability number, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, Basic perfect graphs and their extensions, Chromatic bounds for some classes of \(2 K_2\)-free graphs, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Polyhedral results on the stable set problem in graphs containing even or odd pairs, On a connection between facility location and perfect graphs, Approximability of clique transversal in perfect graphs, On forbidden induced subgraphs for unit disk graphs, Precoloring extension of co-Meyniel graphs, On \(P_4\)-transversals of chordal graphs, The stable set polytope for some extensions of \(P_4\)-free graphs, The \(\langle t \rangle \)-property of some classes of graphs, Constructions for normal graphs and some consequences, Even pairs in Berge graphs, The sandwich problem for decompositions and almost monotone properties, On the inapproximability of independent domination in \(2P_3\)-free perfect graphs, The price of connectivity for cycle transversals, Recognizing vertex intersection graphs of paths on bounded degree trees, Automated generation of conjectures on forbidden subgraph characterization, Algorithms for unipolar and generalized split graphs, Duality for semiantichains and unichain coverings in products of special posets, Game-perfect graphs, Partial characterizations of coordinated graphs: Line graphs and complements of forests, Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs, On the set covering polyhedron of circulant matrices, Characterizing and bounding the imperfection ratio for some classes of graphs, Coloring Artemis graphs, Independence polynomials of circulants with an application to music, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, Triangle-free strongly circular-perfect graphs, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences, Maximum weight independent sets in hole- and co-chair-free graphs, Split digraphs, Combinatorial optimization with 2-joins, The structure of bull-free graphs I -- three-edge-paths with centers and anticenters, Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Vertex- and edge-minimal and locally minimal graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Partitioning graphs into complete and empty graphs, On algorithms for (\(P_5\), gem)-free graphs, Colouring graphs with no induced six-vertex path or diamond, Claw‐free circular‐perfect graphs, Parameters of the coprime graph of a group, Fast Skew Partition Recognition, Component Acquisition Games, Digraphs and Variable Degeneracy, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, The M-intersection graph of ideals of a commutative ring, Counting Small Induced Subgraphs Satisfying Monotone Properties, A limit theorem for the Shannon capacities of odd cycles. II, Simultaneously dominating all spanning trees of a graph, The matrix Jacobson graph of finite commutative rings, Hereditary Efficiently Dominatable Graphs, Structural properties of super strongly perfect graphs, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, Hadwiger's Conjecture for Graphs with Forbidden Holes, $t$-Perfection in $P_5$-Free Graphs, Structure of super strongly perfect graphs, Some properties of subgroup complementary addition Cayley graphs on abelian groups, Circular-imperfection of triangle-free graphs, The Induced Disjoint Paths Problem, Resource convertibility and ordered commutative monoids, A study of enhanced power graphs of finite groups, Easily Testable Graph Properties, Perfect non-commuting graphs of matrices over chains, Hybrid Tractable Classes of Constraint Problems, Enhanced power graphs of groups are weakly perfect, On the zero-divisor graphs of finite free semilattices, Odd Holes in Bull-Free Graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, The polynomial dichotomy for three nonempty part sandwich problems, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, The polynomial dichotomy for three nonempty part sandwich problems, THE JACOBSON GRAPH OF COMMUTATIVE RINGS, Graphs defined on groups, A tutorial on branch and cut algorithms for the maximum stable set problem, The Structure of Claw‐Free Perfect Graphs, Graph transformations preserving the stability number, The order supergraph of the power graph of a finite group, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Disjoint clique cutsets in graphs without long holes, A structure theorem for graphs with no cycle with a unique chord and its consequences, FindingH-partitions efficiently, The perfection and recognition of bull-reducible Berge graphs, Fast distributed algorithms for testing graph properties, On minimal forbidden subgraph characterizations of balanced graphs, Graph transformations preserving the stability number, Algorithmic bounds for the chromatic number†, On the chromatic number of (P_{5},windmill)-free graphs, On subspace inclusion graph of a vector space, Some structural graph properties of the non-commuting graph of a class of finite Moufang loops, Bounding the clique-width of \(H\)-free split graphs, \(k\)-critical graphs in \(P_5\)-free graphs, On 3-coloring of \((2P_4,C_5)\)-free graphs, \(k\)-critical graphs in \(P_5\)-free graphs, The coloring of the cozero-divisor graph of a commutative ring, On 3-coloring of \((2P_4,C_5)\)-free graphs, On graphs with the smallest eigenvalue at least −1 − √2, part III, Clique-perfectness of complements of line graphs, Claw-free circular-perfect graphs, On minimal forbidden subgraph characterizations of balanced graphs, Implosive graphs: Square-free monomials on symbolic Rees algebras, Normal subgroup based power graphs of a finite group, Colouring clique-hypergraphs of circulant graphs, Counting Perfect Matchings and the Switch Chain, Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, Colouring graphs with no induced six-vertex path or diamond, OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT GRAPHS, Complexity of clique-coloring odd-hole-free graphs, Metrically homogeneous graphs of diameter 3, Algorithms on Subtree Filament Graphs, Path-Bicolorable Graphs, Induced Embeddings into Hamming Graphs., Counting Weighted Independent Sets beyond the Permanent, THE CHARACTER GRAPH OF A FINITE GROUP IS PERFECT, Envy-free pricing in multi-item markets, Perfect Digraphs, A new characterization of trivially perfect graphs, On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five, Graph Classes and Forbidden Patterns on Three Vertices, Unnamed Item, On the enhanced power graph of a finite group, The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair, The Inclusion Ideal Graph of Rings, On eternal domination and Vizing-type inequalities, On enhanced power graphs of certain groups, Brilliance or steadiness? A suggestion of an alternative model to Hardy's model concerning golf (1945), Fractional Chromatic Number, Maximum Degree, and Girth, Unnamed Item, Recent developments on the power graph of finite groups – a survey, On the structure of self-complementary graphs, Characterization and recognition of Helly circular-arc clique-perfect graphs, 2K2-Partition Problem, On strongly circular-perfectness, Colouring Some Classes of Perfect Graphs Robustly, Matrix Partitions with Finitely Many Obstructions, Faster 3-Coloring of Small-Diameter Graphs, Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, The Hamiltonian properties in \(K_{1,r}\)-free split graphs, Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4, Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case, One-three join: a graph operation and its consequences, On coloring a class of claw-free graphs., On standard quadratic programs with exact and inexact doubly nonnegative relaxations, The story of perfectly orderable graphs, On the density of trigraph homomorphisms, Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs, Detecting 2-joins faster, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, \( \chi \)-diperfect digraphs, On the chromatic number of some \(P_5\)-free graphs, Some results on Berge's conjecture and begin-end conjecture, 2-divisibility of some odd hole free graphs, On the structure of graphs without claw, \(4K_1\) and co-R, Vertex deletion into bipartite permutation graphs, Coloring graph classes with no induced fork via perfect divisibility, On chordal and perfect plane near-triangulations, Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, Structural properties of Toeplitz graphs, Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, 4-coloring \((P_6, \text{bull})\)-free graphs, On bounding the difference between the maximum degree and the chromatic number by a constant, 3-colouring for dually chordal graphs and generalisations, On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. II: Structure theorem, Color-line and proper color-line graphs, The Hadwiger number, chordal graphs and \(ab\)-perfection, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Small edge sets meeting all triangles of a graph, On the complexity of cd-coloring of graphs, Forbidden induced subgraphs, On some graph classes related to perfect graphs: a survey, Complexity-separating graph classes for vertex, edge and total colouring, 3-colouring AT-free graphs in polynomial time, Independent sets, cliques, and colorings in graphons, Game-perfect digraphs, The clique problem with multiple-choice constraints under a cycle-free dependency graph, Bounds on regularity of quadratic monomial ideals, A local characterization for perfect plane near-triangulations, Automata for the verification of monadic second-order graph properties, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, Integer decomposition property for Cayley sums of order and stable set polytopes, On circular-perfect graphs: a survey, In memoriam: Professor Robin Thomas (1962--2020), A better upper bound on the chromatic number of (cap, even-hole)-free graphs, Erdős-Hajnal for cap-free graphs, An SDP primal-dual algorithm for approximating the Lovász-theta function, On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs, Critical kernel imperfect problem in generalizations of bipartite tournaments, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem, Constructions of \(k\)-critical \(P_5\)-free graphs, A combinatorial approach to nonlocality and contextuality, Polynomial time algorithm for min-ranks of graphs with simple tree structures, Small 1-defective Ramsey numbers in perfect graphs, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Polyhedral properties of the induced cluster subgraphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Independent sets and hitting sets of bicolored rectangular families, Obstructions for three-coloring graphs without induced paths on six vertices, Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded, Graphs without five-vertex path and four-vertex cycle, Some indices over a new algebraic graph, Reconfiguration graph for vertex colourings of weakly chordal graphs, Forbidden subgraphs of power graphs, On the commuting graph of semidihedral group, The intersection of two vertex coloring problems, Online coloring a token graph, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, On superperfection of edge intersection graphs of paths, Hajós and Ore constructions for digraphs, On the linear extension complexity of stable set polytopes for perfect graphs, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Erdős-Lovász Tihany conjecture for graphs with forbidden holes, Recolouring weakly chordal graphs and the complement of triangle-free graphs, Counting edge-injective homomorphisms and matchings on restricted graph classes, Structure of cubic Lehman matrices, Set characterizations and convex extensions for geometric convex-hull proofs, On coloring a class of claw-free and hole-twin-free graphs, Forbidden subgraphs in generating graphs of finite groups, Perfectly relating the domination, total domination, and paired domination numbers of a graph, Subspace-based subspace sum graph on vector spaces, Universally balanced combinatorial optimization games, On the dominating (induced) cycles of iterated line graphs, The reflexive dimension of (0, 1)-polytopes, A faster algorithm to recognize even-hole-free graphs, A note on a conjecture of Wu, Xu and Xu, Generalizing cographs to 2-cographs, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets, \(\alpha\)-diperfect digraphs, Coloring of \((P_5, 4\)-wheel)-free graphs, Partitioning a graph into disjoint cliques and a triangle-free graph, Point partition numbers: perfect graphs, Game-perfect semiorientations of forests
