Wyniki wyszukiwania

1

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

EN

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.

2

Vertex coloring the square of outerplanar graphs of low degree

100%

Agnarsson G., Halldórsson M.

Discussiones Mathematicae Graph Theory

|

2010

|

tom 30

|

nr 4

619-636

EN

Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

3

The Degree-Diameter Problem for Outerplanar Graphs

75%

Dankelmann P., Jonck E., Vetrík T.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 3

823-834

EN

For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) $n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2} - 1} } \right)$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) $n_{\Delta ,D} = 3\Delta ^{{{D - 1} \over 2}} + O\left( {\Delta ^{{{D - 1} \over 2} - 1} } \right)$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Agnarsson G.

1 Dankelmann P.

1 Halldórsson M.

1 Jonck E.

1 Mitchem J.

1 Morriss P.

1 Schmeichel E.

1 Vetrík T.

1 2017

1 2010

1 1997

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

Vertex coloring the square of outerplanar graphs of low degree

The Degree-Diameter Problem for Outerplanar Graphs