Displaying similar documents to “A new proof of the four-colour theorem.”

The list linear arboricity of planar graphs

Xinhui An, Baoyindureng Wu (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9. ...

Planar Ramsey numbers

Izolda Gorgol (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.

On transitive orientations of G-ê

Michael Andresen (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

The edge C₄ graph of some graph classes

Manju K. Menon, A. Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices,...