Fetching the paper…

Reading the bibliography…

Independent sets and cuts in large-girth regular graphs · Around

2016

Independent sets and cuts in large-girth regular graphs

Csóka, Endre

Original
PDF
Post on X

Understand

We present a local algorithm producing an independent set of expected size $0.44533n$ on large-girth 3-regular graphs and $0.40407n$ on large-girth 4-regular graphs.

We also construct a cut (or bisection or bipartite subgraph) with $1.34105n$ edges on large-girth 3-regular graphs.
These decrease the gaps between the best known upper and lower bounds from $0.0178$ to $0.01$, from $0.0242$ to $0.0123$ and from $0.0724$ to $0.0616$, respectively.
We are using local algorithms, therefore, the method also provides upper bounds for the fractional coloring numbers of $1 / 0.44533 \approx 2.24554$ and $1 / 0.40407 \approx 2.4748$ and fractional edge coloring number $1.5 / 1.34105 \approx 1.1185$.

Built on

The independence ratio of regular graphs
Béla Bollobás · 1981
Earlier work this paper cites.
Maximum bipartite subgraphs of regular graphs with large girth
Brendan D McKay · 1982
Earlier work this paper cites.
A note on the independence number of triangle-free graphs
James B Shearer · 1983
Earlier work this paper cites.
Independent sets in regular graphs of high girth
B. D. McKay · 1987
Earlier work this paper cites.
Bisection of random cubic graphs
Josep Díaz, Norman Do, MJ Sernal, and Nicholas C Wormald · 2002
Earlier work this paper cites.

Similar

Bipartite subgraphs in a random cubic graph
Jan Hladkỳ · 2006
Cited alongside, same era.
Properties of graphs with large girth
Carlos Hoppen · 2008
Cited alongside, same era.
A conjecture on the maximum cut and bisection width in random regular graphs
Original
Lenka Zdeborová and Stefan Boettcher · 2010
Cited alongside, same era.
Fractional colorings of cubic graphs with large girth
František Kardoš, Daniel Král’, and Jan Volec · 2011
Cited alongside, same era.

Then

Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
František Kardoš, Daniel Král’, and Jan Volec · 2012
Later among the works it cites.
Local algorithms, regular graphs of large girth, and random regular graphs
Original
Carlos Hoppen and Nicholas Wormald · 2013
Later among the works it cites.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Later among the works it cites.
Invariant gaussian processes and independent sets on regular graphs of large girth
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…