Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: planar

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On the cost chromatic number of outerplanar, planar, and line graphs

100%

Mitchem J., Morriss P., Schmeichel E.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 2

229-241

We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct several infinite classes of counterexamples to a conjecture of Harary and Plantholt on the cost chromatic number of line graphs.

Split Euler Tours In 4-Regular Planar Graphs

88%

Couch P., Daniel B. D., Guidry R., Paul Wright W.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

23-30

The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Couch P.

1 Daniel B. D.

1 Guidry R.

1 Mitchem J.

1 Morriss P.

1 Paul Wright W.

1 Schmeichel E.

1 2016

1 1997

Wyniki wyszukiwania

On the cost chromatic number of outerplanar, planar, and line graphs

Split Euler Tours In 4-Regular Planar Graphs