Vertex- and edge-minimal and locally minimal graphs

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

zbMATH Keywords

chromatic numberkernelclique numberodd holescomplementary connected graphslocally edge-minimallocally vertex-minimalodd anti-holesperfect and imperfect graphsRotterdam graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40)

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