Matching cut and girth

Importance: Medium ✭✭
Author(s):
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: w
on: November 30th, 2011

\begin{question} For every $d$ does there exists a $g$ such that every graph with average degree smaller than $d$ and girth at least $g$ has a matching-cut? \end{question}

Let $G=(V,E)$ be a graph. A matching $M$ is a matching-cut if there exists a set $S\subset V$ such that $M = E(S:V\setminus S)$. Graphs having a matching-cut are called decomposable.

It is known that every graph with $|E| < 3(|V|-1)/2$ is decomposable [BFP11].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [C84] V. Chvátal, Recognizing decomposable graphs, J Graph Theory 8 (1984), 51–53

[BFP11] P. Bonsma, A. Farley, A. Proskurowski, Extremal graphs having no matching cuts, J Graph Theory (2011)


* indicates original appearance(s) of problem.