Vertex- and edge-minimal and locally minimal graphs
From MaRDI portal
Publication:1043552
DOI10.1016/j.disc.2008.10.020zbMath1229.05131OpenAlexW2152893907WikidataQ59560578 ScholiaQ59560578MaRDI QIDQ1043552
Endre Boros, Vladimir A. Gurvich
Publication date: 9 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2008.10.020
chromatic numberkernelclique numberodd holescomplementary connected graphslocally edge-minimallocally vertex-minimalodd anti-holesperfect and imperfect graphsRotterdam graphs
Related Items (6)
Friendship two-graphs ⋮ On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems ⋮ Not complementary connected and not CIS \(d\)-graphs form weakly monotone families ⋮ Decomposing complete edge-chromatic graphs and hypergraphs. Revisited ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ Minimal and locally minimal games and game forms
Cites Work
- The strong perfect graph theorem
- Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
- Perfect graphs are kernel solvable
- Graphical properties related to minimal imperfection
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
- Some simplified NP-complete graph problems
- A corrected version of the Duchet kernel conjecture
- A circular graph---counterexample to the Duchet kernel conjecture
- Graphs indecomposable with respect to the X-join
- Recognizing Berge graphs
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- Recent problems and results about kernels in directed graphs
- Solutions of irreflexive relations
- Graphes Noyau-Parfaits
- Recursive generation of partitionable graphs
- Transitiv orientierbare Graphen
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Vertex- and edge-minimal and locally minimal graphs
