Oleg V. Borodin, Anna O. Ivanova (2013)
Discussiones Mathematicae Graph Theory
Similarity:
We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
Sebastian Urbański (1996)
Discussiones Mathematicae Graph Theory
Similarity:
The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K₅.
Felsner, Stefan, Massow, Mareike (2008)
Journal of Graph Algorithms and Applications
Similarity:
Yuehua Bu, Ko-Wei Lih, Weifan Wang (2011)
Discussiones Mathematicae Graph Theory
Similarity:
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu,...
Juvan, Martin, Mohar, Bojan, Thomas, Robin (1999)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Jin, Zemin, Li, Xueliang (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Hetherington, Timothy J., Woodall, Douglas R. (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Grytczuk, Jarosław (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Luczak, Tomasz (1994)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
LeSaulnier, Timothy D., Stocker, Christopher, Wenger, Paul S., West, Douglas B. (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Balogh, József, Martin, Ryan (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Xin Zhang, Yong Yu, Guizhen Liu (2011)
Open Mathematics
Similarity:
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.
Alexander Halperin, Colton Magnant, Kyle Pula (2014)
Discussiones Mathematicae Graph Theory
Similarity:
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed...