Displaying similar documents to “Crossings, colorings, and cliques.”

On the Independence Number of Edge Chromatic Critical Graphs

Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)

A maximum degree theorem for diameter-2-critical graphs

Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)

Open Mathematics

Similarity:

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where...

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

Similarity:

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As...

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On (p, 1)-total labelling of 1-planar graphs

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.

The structure of plane graphs with independent crossings and its applications to coloring problems

Xin Zhang, Guizhen Liu (2013)

Open Mathematics

Similarity:

If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity...