Results 1 to 10 of about 116,505 (190)
An Ore-type Theorem for Perfect Packings in Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2009 23 pages, 1 figure. Extra examples and a sketch proof of Theorem 4 added.
Daniela Kühn +2 more
core +5 more sources
The strong perfect graph theorem [PDF]
Annals of Mathematics, 2006 A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A
Maria Chudnovsky +3 more
openalex +3 more sources
A constructive formalization of the weak perfect graph theorem [PDF]
Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, 2020 The 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020)
Abhishek Kr Singh, Raja Natarajan
openalex +4 more sources
Electronic Journal of Graph Theory and Applications, 2017 In decomposition theory, extreme sets have been studied extensively due to its connection to perfect matchings in a graph. In this paper, we first define extreme sets with respect to degree-matchings and next investigate some of their properties.
Radosław Cymer
doaj +3 more sources
Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs [PDF]
, 2019 A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian ...
Meike Hatzel +2 more
openalex +4 more sources
A weak box-perfect graph theorem
Journal of Combinatorial Theory, Series BzbMATH Open Web Interface contents unavailable due to conflicting licenses.
Patrick Chervet, Roland Grappe
openalex +3 more sources
Towards a Constructive Formalization of Perfect Graph Theorems [PDF]
, 2019 ICLA ...
Abhishek Kr Singh, Raja Natarajan
openalex +3 more sources
A semi-strong Perfect Graph theorem
Journal of Combinatorial Theory, Series B, 1987 The perfectness of a graph G was defined by Berge in 1961. He also proposed the following two conjectures: (1) G is perfect if and only if it contains no induced subgraph isomorphic to an odd cycle of length greater than three or the complement of such a cycle (strong perfect graph conjecture) and (2) G is perfect if and only if \(\bar G\) is perfect ...
Bruce Reed
openalex +3 more sources
A Complementation Theorem for Perfect Matchings of Graphs Having a Cellular Completion
Journal of Combinatorial Theory, Series A, 1998 A graph whose edges can be partitioned into 4-cycles in such a way that each vertex is contained in at most two 4-cycles is called a cellular graph. The author gives a ``complementation theorem'' for enumerating the matchings of certain subgraphs of cellular graphs.
Mihai Ciucu
openalex +2 more sources