Displaying similar documents to “A Note On Vertex Colorings Of Plane Graphs”

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

A note on face coloring entire weightings of plane graphs

Stanislav Jendrol, Peter Šugerek (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

Gallai and anti-Gallai graphs of a graph

S. Aparna Lakshmanan, S. B. Rao, A. Vijayakumar (2007)

Mathematica Bohemica

Similarity:

The paper deals with graph operators—the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H -free for any finite graph H . The case of complement reducible graphs—cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.