Temat: planar graph - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs
Autorzy:: Bielak, Halina
Tematy:: planar graph
Ramsey number; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744142.pdf Link otwiera się w nowym oknie
Opis:: We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: On Longest Cycles in Essentially 4-Connected Planar Graphs
Autorzy:: Fabrici, Igor
Harant, Jochen
Jendroľ, Stanislav
Tematy:: planar graph
longest cycle; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31340878.pdf Link otwiera się w nowym oknie
Opis:: A planar 3-connected graph $ G $ is essentially 4-connected if, for any 3-separator $ S $ of $ G $, one component of the graph obtained from $ G $ by removing $ S $ is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle $ C $ such that $ |V(C)| \ge \frac{2n+4}{5} $. For a cubic essentially 4-connected planar graph $G$, Grünbaum with Malkevitch, and Zhang showed that $G$ has a cycle on at least $ \frac{3}{4} n $ vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of $G$ are presented if $G$ is an essentially 4-connected planar graph of maximum degree 4 or $G$ is an essentially 4-connected maximal planar graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: On properties of maximal 1-planar graphs
Autorzy:: Hudák, Dávid
Madaras, Tomáš
Suzuki, Yusuke
Tematy:: 1-planar graph
maximal graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743290.pdf Link otwiera się w nowym oknie
Opis:: 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Light Graphs In Planar Graphs Of Large Girth
Autorzy:: Hudák, Peter
Maceková, Mária
Madaras, Tomáš
Široczki, Pavol
Tematy:: planar graph
girth
light graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341096.pdf Link otwiera się w nowym oknie
Opis:: A graph $ H $ is defined to be light in a graph family if there exist finite numbers $ \phi (H, \mathcal{G} ) $ and $ w(H,\mathcal{G} ) $ such that each $ G \in \mathcal{G} $ which contains $ H $ as a subgraph, also contains its isomorphic copy $ K $ with $ \Delta_G (K) \le \phi (H, \mathcal{G} ) $ and $ \Sigma_{ x \in V(K) } \text{ deg}_G (x) \le w(H, \mathcal{G}) $. 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 $ \phi $ and w for light $ K_{1,3} $ and $ C_{10} $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Planar graphs have bounded nonrepetitive chromatic number
Autorzy:: Joret, Gwenaël
Wood, David R.
Dujmović, Vida
Esperet, Louis
Walczak, Bartosz
Opis:: A colouring of a graph isnonrepetitiveif for every path of even order, thesequence of colours on the first half of the path is different from the sequence of colours onthe second half. We show that planar graphs have nonrepetitive colourings with a boundednumber of colours, thus proving a conjecture of Alon, Grytczuk, Hałuszczak and Riordan(2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding afixed minor, and graphs excluding a fixed topological minor.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
Autorzy:: Czap, Július
Przybyło, Jakub
Škrabuľáková, Erika
Tematy:: 1-planar graph
bipartite graph
graph size; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341143.pdf Link otwiera się w nowym oknie
Opis:: A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Planar graphs without 4-, 5- and 8-cycles are 3-colorable
Autorzy:: Mondal, Sakib
Tematy:: 3-coloring
planar graph
discharging; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743615.pdf Link otwiera się w nowym oknie
Opis:: In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4
Autorzy:: Hasheminezhad, Mahdieh
McKay, Brendan
Tematy:: planar graph
octahedrite
quadrangulation
generation; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744545.pdf Link otwiera się w nowym oknie
Opis:: We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Non-1-Planarity of Lexicographic Products of Graphs
Autorzy:: Matsumoto, Naoki
Suzuki, Yusuke
Tematy:: 1-planar graph
lexicographic product; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32222720.pdf Link otwiera się w nowym oknie
Opis:: In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K₂. This result completes the proof of the conjecture that a graph G ◦ K₂ is 1-planar if and only if G has no edge belonging to two cycles.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: Light edges in 1-planar graphs with prescribed minimum degree
Autorzy:: Hudák, Dávid
Šugerek, Peter
Tematy:: light edge
1-planar graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743256.pdf Link otwiera się w nowym oknie
Opis:: A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains just the selected edge type).
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "planar graph" wg kryterium: Temat