Displaying similar documents to “On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs”

Characterizations of planar plick graphs

V.R. Kulli, B. Basavanagoud (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we present characterizations of graphs whose plick graphs are planar, outerplanar and minimally nonouterplanar.

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Oleg V. Borodin, Anna O. Ivanova (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

Light Graphs In Planar Graphs Of Large Girth

Peter Hudák, Mária Maceková, Tomáš Madaras, Pavol Široczki (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w...

On properties of maximal 1-planar graphs

Dávid Hudák, Tomáš Madaras, Yusuke Suzuki (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called 1-planar if there exists a drawing in the plane so that each edge contains at most one crossing. We study maximal 1-planar graphs from the point of view of properties of their diagrams, local structure and hamiltonicity.

4-chromatic Koester graphs

Andrey A. Dobrynin, Leonid S. Mel'nikov (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples...

Decompositions of quadrangle-free planar graphs

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh (2009)

Discussiones Mathematicae Graph Theory

Similarity:

W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.

The Thickness of Amalgamations and Cartesian Product of Graphs

Yan Yang, Yichao Chen (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been known for only few graphs. We obtain the thickness of vertex-amalgamation and bar-amalgamation of graphs, the lower and upper bounds for the thickness of edge-amalgamation and 2-vertex-amalgamation of graphs, respectively. We also study...

Bar k -visibility graphs.

Dean, Alice M., Evans, William, Gethner, Ellen, Laison, Joshua D., Safari, Mohammad Ali, Trotter, William T. (2007)

Journal of Graph Algorithms and Applications

Similarity:

More on even [a,b]-factors in graphs

Abdollah Khodkar, Rui Xu (2007)

Discussiones Mathematicae Graph Theory

Similarity:

In this note we give a characterization of the complete bipartite graphs which have an even (odd) [a,b]-factor. For general graphs we prove that an a-edge connected graph G with n vertices and with δ(G) ≥ max{a+1,an/(a+b) + a - 2} has an even [a,b]-factor, where a and b are even and 2 ≤ a ≤ b. With regard to the edge-connectivity this result is slightly better than one of the similar results obtained by Kouider and Vestergaard in 2004 and unlike their results, this result has no restriction...