Displaying similar documents to “Planar Ramsey numbers”

Strong Edge-Coloring Of Planar Graphs

Wen-Yao Song, Lian-Ying Miao (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by 𝜒's(G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4 Δ(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211]. In this paper, we show that...

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

Július Czap, Zsolt Tuza (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial...

M 2 -Edge Colorings Of Cacti And Graph Joins

Július Czap, Peter Šugerek, Jaroslav Ivančo (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.

Light edges in 1-planar graphs with prescribed minimum degree

Dávid Hudák, Peter Šugerek (2012)

Discussiones Mathematicae Graph Theory

Similarity:

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...

A new proof of the four-colour theorem.

Robertson, Neil, Sanders, Daniel P., Seymour, Paul, Thomas, Robin (1996)

Electronic Research Announcements of the American Mathematical Society [electronic only]

Similarity:

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Hamiltonicity and Generalised Total Colourings of Planar Graphs

Mieczysław Borowiecki, Izak Broere (2016)

Discussiones Mathematicae Graph Theory

Similarity:

The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers...

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: