Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: subcubic graph

Sortuj według:

Ogranicz wyniki do:

Interval Incidence Coloring of Subcubic Graphs

100%

Małafiejska A., Małafiejski M.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 2

427-441

In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.

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

2-distance 4-colorability of planar subcubic graphs with girth at least 22

100%

Borodin O., Ivanova A.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 1

141-151

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Borodin O.

1 Ivanova A.

1 Małafiejska A.

1 Małafiejski M.

1 2017

1 2012

Wyniki wyszukiwania

Interval Incidence Coloring of Subcubic Graphs

2-distance 4-colorability of planar subcubic graphs with girth at least 22