Displaying similar documents to “Strong Chromatic Index Of Planar Graphs With Large Girth”

Orthogonal vector coloring.

Haynes, Gerald, Park, Catherine, Schaeffer, Amanda, Webster, Jordan, Mitchell, Lon H. (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Two linear time algorithms for MST on minor closed graph classes

Martin Mareš (2004)

Archivum Mathematicum

Similarity:

This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in O ( | V | + | E | ) time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.

A Note On Vertex Colorings Of Plane Graphs

Igor Fabricia, Stanislav Jendrol’, Roman Soták (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.