On balanced graphs

DOI10.1007/S10107-005-0651-YMaRDI QIDQ2583124zbMATH OpenOpenAlexFDO

Authors Guillermo Durán, Min Chih Lin, Flavia Bonomo, Jayme L. Szwarcfiter

Publication date 13 January 2006

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10533/177630

zbMATH Keywords

0-1 matricesAlgorithmsBalanced hypergraphsClique graphsDomination

Mathematics Subject Classification ID

Perfect graphs (05C17) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On minimal forbidden subgraph characterizations of balanced graphs
• On minimal forbidden subgraph characterizations of balanced graphs
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• A polynomial recognition algorithm for balanced matrices
• Balancedness of subclasses of circular-arc graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A partial characterization of clique graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic graph theory and perfect graphs
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Balanced matrices
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Combinatorial optimization. Packing and covering
• Decomposition of balanced matrices
• scientific article; zbMATH DE number 3427408 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 4199652 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 1944140 (Why is no real title available?)
• scientific article; zbMATH DE number 1750103 (Why is no real title available?)
• scientific article; zbMATH DE number 863476 (Why is no real title available?)
• scientific article; zbMATH DE number 3363617 (Why is no real title available?)
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• Neighborhood perfect graphs
• On certain polytopes associated with graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Über iterierte Clique-Graphen

Cited in

(31)

• The generalized independent set problem: polyhedral analysis and solution approaches
• Mengerian quasi-graphical families and clutters
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• On some graph classes related to perfect graphs: a survey
• The clique-perfectness and clique-coloring of outer-planar graphs
• Variations of maximum-clique transversal sets on graphs
• Solution of three problems of Cornuéjols
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Balancedness of some subclasses of circular-arc graphs
• Clique-perfectness and balancedness of some graph classes
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• A unified approach to recognize squares of split graphs
• Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• scientific article; zbMATH DE number 5543097 (Why is no real title available?)
• Integrality properties of certain special balanceable families
• Every graph is contained in a sparsest possible balanced graph
• Weighted maximum-clique transversal sets of graphs
• Graphs with the balas—uhry property
• The clique-transversal set problem in claw-free graphs with degree at most 4
• Clique-perfectness of claw-free planar graphs
• CFI Construction and Balanced Graphs
• scientific article; zbMATH DE number 6302886 (Why is no real title available?)
• Structure of the Group of Balanced Labelings on Graphs, its Subgroups and Quotient Groups
• scientific article; zbMATH DE number 7332479 (Why is no real title available?)
• On minimal forbidden subgraph characterizations of balanced graphs
• On minimal forbidden subgraph characterizations of balanced graphs
• Algorithms for finding clique-transversals of graphs
• Bounds on the clique-transversal number of regular graphs

This page was built for publication: On balanced graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583124)