Displaying similar documents to “Mácajová and Škoviera conjecture on cubic graphs”

Cores, Joins and the Fano-Flow Conjectures

Ligang Jin, Eckhard Steffen, Giuseppe Mazzuoccolo (2018)

Discussiones Mathematicae Graph Theory

Similarity:

The Fan-Raspaud Conjecture states that every bridgeless cubic graph has three 1-factors with empty intersection. A weaker one than this conjecture is that every bridgeless cubic graph has two 1-factors and one join with empty intersection. Both of these two conjectures can be related to conjectures on Fano-flows. In this paper, we show that these two conjectures are equivalent to some statements on cores and weak cores of a bridgeless cubic graph. In particular, we prove that the Fan-Raspaud...

Some recent results on domination in graphs

Michael D. Plummer (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; ...

On generating snarks

Busiso P. Chisala (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We discuss the construction of snarks (that is, cyclically 4-edge connected cubic graphs of girth at least five which are not 3-edge colourable) by using what we call colourable snark units and a welding process.

On the Erdős-Gyárfás Conjecture in Claw-Free Graphs

Pouria Salehi Nowbandegani, Hossein Esfandiari, Mohammad Hassan Shirdareh Haghighi, Khodakhast Bibak (2014)

Discussiones Mathematicae Graph Theory

Similarity:

The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

Some remarks on Jaeger's dual-hamiltonian conjecture

Bill Jackson, Carol A. Whitehead (1999)

Annales de l'institut Fourier

Similarity:

François Jaeger conjectured in 1974 that every cyclically 4-connected cubic graph G is dual hamiltonian, that is to say the vertices of G can be partitioned into two subsets such that each subset induces a tree in G . We shall make several remarks on this conjecture.

A Survey of the Path Partition Conjecture

Marietjie Frick (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.