BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jan Goedgebeur

Jan Goedgebeur appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete Mathematicsphysics.comp-ph

Catalog footprint

What is connected

13works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2020arXiv

$k$-Critical Graphs in $P_5$-Free Graphs

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we initiate a systematic study of the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworth's Theorem -- that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large independent sets in triangle-free cubic graphs: beyond planarity

Every $n$-vertex planar triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$. This was first conjectured by Albertson, Bollobás and Tucker, and was later proved by Heckman and Thomas. Fraughnaugh and Locke conjectured that the planarity requirement could be relaxed into just forbidding a few specific nonplanar subgraphs: They described a family $\mathcal{F}$ of six nonplanar graphs (each of order at most $22$) and conjectured that every $n$-vertex triangle-free graph with maximum degree at most $3$ having no subgraph isomorphic to a member of $\mathcal{F}$ has an independent set of size at least $\frac{3}{8}n$. In this paper, we prove this conjecture. As a corollary, we obtain that every $2$-connected $n$-vertex triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$, with the exception of the six graphs in $\mathcal{F}$. This confirms a conjecture made independently by Bajnok and Brinkmann, and by Fraughnaugh and Locke.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Hypohamiltonian Snarks and a Theorem of Fiorini

We discuss an omission in the statement and proof of Fiorini's 1983 theorem on hypohamiltonian snarks and present a version of this theorem which is more general in several ways. Using Fiorini's erroneous result, Steffen showed that hypohamiltonian snarks exist for some $n \ge 10$ and each even $n \ge 92$. We rectify Steffen's proof by providing a correct demonstration of a technical lemma on flower snarks, which might be of separate interest. We then strengthen Steffen's theorem to the strongest possible form by determining all orders for which hypohamiltonian snarks exists. This also strengthens a result of Máčajová and Škoviera. Finally, we verify a conjecture of Steffen on hypohamiltonian snarks up to 36 vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A counterexample to the pseudo 2-factor isomorphic graph conjecture

A graph $G$ is pseudo 2-factor isomorphic if the parity of the number of cycles in a 2-factor is the same for all 2-factors of $G$. Abreu et al. conjectured that $K_{3,3}$, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs (Abreu et al., Journal of Combinatorial Theory, Series B, 2008, Conjecture 3.6). Using a computer search we show that this conjecture is false by constructing a counterexample with 30 vertices. We also show that this is the only counterexample up to at least 40 vertices. A graph $G$ is 2-factor hamiltonian if all 2-factors of $G$ are hamiltonian cycles. Funk et al. conjectured that every 2-factor hamiltonian cubic bipartite graph can be obtained from $K_{3,3}$ and the Heawood graph by applying repeated star products (Funk et al., Journal of Combinatorial Theory, Series B, 2003, Conjecture 3.2). We verify that this conjecture holds up to at least 40 vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Exhaustive generation of $k$-critical $\mathcal H$-free graphs

We describe an algorithm for generating all $k$-critical $\mathcal H$-free graphs, based on a method of Hoàng et al. Using this algorithm, we prove that there are only finitely many $4$-critical $(P_7,C_k)$-free graphs, for both $k=4$ and $k=5$. We also show that there are only finitely many $4$-critical graphs $(P_8,C_4)$-free graphs. For each case of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the $3$-colorability problem in the respective classes. Moreover, we prove that for every $t$, the class of 4-critical planar $P_t$-free graphs is finite. We also determine all 27 4-critical planar $(P_7,C_6)$-free graphs. We also prove that every $P_{10}$-free graph of girth at least five is 3-colorable, and determine the smallest 4-chromatic $P_{12}$-free graph of girth five. Moreover, we show that every $P_{13}$-free graph of girth at least six and every $P_{16}$-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fullerenes with distant pentagons

For each $d>0$, we find all the smallest fullerenes for which the least distance between two pentagons is $d$. We also show that for each $d$ there is an $h_d$ such that fullerenes with pentagons at least distance $d$ apart and any number of hexagons greater than or equal to $h_d$ exist. We also determine the number of fullerenes where the minimum distance between any two pentagons is at least $d$, for $1 \le d \le 5$, up to 400 vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Recursive generation of IPR fullerenes

We describe a new construction algorithm for the recursive generation of all non-isomorphic IPR fullerenes. Unlike previous algorithms, the new algorithm stays entirely within the class of IPR fullerenes, that is: every IPR fullerene is constructed by expanding a smaller IPR fullerene unless it belongs to limited class of irreducible IPR fullerenes that can easily be made separately. The class of irreducible IPR fullerenes consists of 36 fullerenes with up to 112 vertices and 4 infinite families of nanotube fullerenes. Our implementation of this algorithm is faster than other generators for IPR fullerenes and we used it to compute all IPR fullerenes up to 400 vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generation and Properties of Snarks

For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for \emph{snarks}, the class of nontrivial 3-regular graphs which cannot be 3-edge coloured. In the first part of this paper we present a new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on $n\leq 36$ vertices. Previously lists up to $n=28$ vertices have been published. In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaeger's Petersen colouring conjecture, which in turn implies that Fulkerson's conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

New Computational Upper Bounds for Ramsey Numbers R(3,k)

Using computational techniques we derive six new upper bounds on the classical two-color Ramsey numbers: R(3,10) <= 42, R(3,11) <= 50, R(3,13) <= 68, R(3,14) <= 77, R(3,15) <= 87, and R(3,16) <= 98. All of them are improvements by one over the previously best known bounds. Let e(3,k,n) denote the minimum number of edges in any triangle-free graph on n vertices without independent sets of order k. The new upper bounds on R(3,k) are obtained by completing the computation of the exact values of e(3,k,n) for all n with k <= 9 and for all n <= 33 for k = 10, and by establishing new lower bounds on e(3,k,n) for most of the open cases for 10 <= k <= 15. The enumeration of all graphs witnessing the values of e(3,k,n) is completed for all cases with k <= 9. We prove that the known critical graph for R(3,9) on 35 vertices is unique up to isomorphism. For the case of R(3,10), first we establish that R(3,10) = 43 if and only if e(3,10,42) = 189, or equivalently, that if R(3,10) = 43 then every critical graph is regular of degree 9. Then, using computations, we disprove the existence of the latter, and thus show that R(3,10) <= 42.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Ramsey Number $R(3,K_{10}-e)$ and Computational Bounds for $R(3,G)$

Using computer algorithms we establish that the Ramsey number $R(3,K_{10}-e)$ is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of $R(3,K_k-e)$ for $11 \le k \le 16$, and show by construction a new lower bound $55 \le R(3,K_{13}-e)$. The new upper bounds on $R(3,K_k-e)$ are obtained by using the values and lower bounds on $e(3,K_l-e,n)$ for $l \le k$, where $e(3,K_k-e,n)$ is the minimum number of edges in any triangle-free graph on $n$ vertices without $K_k-e$ in the complement. We complete the computation of the exact values of $e(3,K_k-e,n)$ for all $n$ with $k \leq 10$ and for $n \leq 34$ with $k = 11$, and establish many new lower bounds on $e(3,K_k-e,n)$ for higher values of $k$. Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely $R(3,K_{10}-K_3-e)=31$ and $R(3,K_{10}-P_3-e)=31$. For graphs $G$ on 10 vertices, %besides $G=K_{10}$, this leaves 6 other open besides $G=K_{10}$, this leaves 6 open cases of the form $R(3,G)$. The hardest among them appears to be $G=K_{10}-2K_2$, for which we establish the bounds $31 \le R(3,K_{10}-2K_2) \le 33$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

House of Graphs: a database of interesting graphs

In this note we present House of Graphs (http://hog.grinvin.org) which is a new database of graphs. The key principle is to have a searchable database and offer -- next to complete lists of some graph classes -- also a list of special graphs that already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Ramsey numbers R(K3,G) for graphs of order 10

In this article we give the generalized triangle Ramsey numbers R(K3,G) of 12 005 158 of the 12 005 168 graphs of order 10. There are 10 graphs remaining for which we could not determine the Ramsey number. Most likely these graphs need approaches focusing on each individual graph in order to determine their triangle Ramsey number. The results were obtained by combining new computational and theoretical results. We also describe an optimized algorithm for the generation of all maximal triangle-free graphs and triangle Ramsey graphs. All Ramsey numbers up to 30 were computed by our implementation of this algorithm. We also prove some theoretical results that are applied to determine several triangle Ramsey numbers larger than 30. As not only the number of graphs is increasing very fast, but also the difficulty to determine Ramsey numbers, we consider it very likely that the table of all triangle Ramsey numbers for graphs of order 10 is the last complete table that can possibly be determined for a very long time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Generation of Fullerenes

We describe an efficient new algorithm for the generation of fullerenes. Our implementation of this algorithm is more than 3.5 times faster than the previously fastest generator for fullerenes -- fullgen -- and the first program since fullgen to be useful for more than 100 vertices. We also note a programming error in fullgen that caused problems for 136 or more vertices. We tabulate the numbers of fullerenes and IPR fullerenes up to 400 vertices. We also check up to 316 vertices a conjecture of Barnette that cubic planar graphs with maximum face size 6 are hamiltonian and verify that the smallest counterexample to the spiral conjecture has 380 vertices.

0 citations0 reviewsNo code linkedOpen access