scientific article; zbMATH DE number 3445275

Publication date: 1974

Full work available at URL: https://eudml.org/doc/16622

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Coloring of graphs and hypergraphs (05C15)

Related Items (only showing first 100 items - show all)

Independent sets of maximum weight in ($p,q$)-colorable graphs. ⋮ Strengthening topological colorful results for graphs ⋮ Disjointness graphs of segments in the space ⋮ On the vertex packing problem ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing weighted subset transversals in $H$-free graphs ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of $P_{5}$-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in $H$-free graphs ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Graphs with a unique maximum independent set up to automorphisms ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ The algorithmic complexity of the minus clique-transversal problem ⋮ On the computational complexity of the virtual network embedding problem ⋮ Some observations on maximum weight stable sets in certain $P_{5}$-free graphs ⋮ Claw-free graphs---a survey ⋮ Tent and a subclass of $P_{5}$-free graphs ⋮ A nice class for the vertex packing problem ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of $2K_2$-free graphs ⋮ Partitioning $H$-free graphs of bounded diameter ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ 1-extendability of independent sets ⋮ Using edge contractions and vertex deletions to reduce the independence number and the clique number ⋮ Threshold Dimension of Graphs ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Trees with maximum number of maximal matchings ⋮ Independent sets in some classes of $S_{i,j,k}$-free graphs ⋮ On atomic structure of $P_5$-free subclasses and maximum weight independent set problem ⋮ Clique cutsets beyond chordal graphs ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Solving the clique cover problem on (bull, $C_4$)-free graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ The cluster deletion problem for cographs ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Finding clubs in graph classes ⋮ Boolean functions with a simple certificate for CNF complexity ⋮ Maximum weight independent sets for ($P_7$,triangle)-free graphs in polynomial time ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Unnamed Item ⋮ Maximum weight independent set for $\ell$claw-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of $P_6$-free graphs ⋮ How (Maximally) Contextual Is Quantum Mechanics? ⋮ A Lower Bound of the cd-Chromatic Number and Its Complexity ⋮ An augmenting graph approach to the stable set problem in $P_{5}$-free graphs ⋮ Distance-$d$ independent set problems for bipartite and chordal graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ $P_{5}$-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs ⋮ Stable sets in $\{\mathrm{ISK4,wheel}\}$-free graphs ⋮ A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ A computational complexity comparative study of graph tessellation problems ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Sum-perfect graphs ⋮ Computing independent sets in graphs with large girth ⋮ Independent feedback vertex set for $P_5$-free graphs ⋮ Stable sets of maximum weight in ($P_{7}$, banner)-free graphs ⋮ $K_{1,3}$-free and $W_4$-free graphs ⋮ Complexity properties of complementary prisms ⋮ On two extensions of equimatchable graphs ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Covering the cliques of a graph with vertices ⋮ Maximum regular induced subgraphs in $2P_3$-free graphs ⋮ Hitting subgraphs in $P_4$-tidy graphs ⋮ 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 ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Maximum independent sets near the upper bound ⋮ Contraction and deletion blockers for perfect graphs and $H$-free graphs ⋮ Inequity aversion pricing over social networks: approximation algorithms and hardness results ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Maximum weight independent sets for ($S_{1,2,4}$,triangle)-free graphs in polynomial time ⋮ Zero forcing in claw-free cubic graphs ⋮ Independent sets in $(P_4+P_4$,triangle)-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ Combinatorial optimization with 2-joins ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Hardness of edge-modification problems ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Revising Johnson's table for the 21st century ⋮ Stable sets in certain $P_6$-free graphs ⋮ On the stable set problem in special $P_{5}$-free graphs ⋮ The conjunctive complexity of quadratic Boolean functions ⋮ On the complexity of the vector connectivity problem ⋮ Vertex cover at distance on $H$-free graphs ⋮ $(p,k)$-coloring problems in line graphs

This page was built for publication: