- Tytuł:
- The use of Eulers formula in (3,1)*-list coloring
- Autorzy:
-
Zhao, Yongqiang
He, Wenjie - Powiązania:
- https://bibliotekanauki.pl/articles/743889.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
list improper coloring
(L,d)*-coloring
(m,d)*-choosable
Euler's formula - Opis:
- A graph G is called (k,d)*-choosable if, for every list assignment L satisfying |L(v)| = k for all v ∈ V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. Ko-Wei Lih et al. used the way of discharging to prove that every planar graph without 4-cycles and i-cycles for some i ∈ {5,6,7} is (3,1)*-choosable. In this paper, we show that if G is 2-connected, we may just use Euler's formula and the graph's structural properties to prove these results. Furthermore, for 2-connected planar graph G, we use the same way to prove that, if G has no 4-cycles, and the number of 5-cycles contained in G is at most $11 + ⎣∑_{i≥5} [(5i-24)/4] |V_i|⎦$, then G is (3,1)*-choosable; if G has no 5-cycles, and any planar embedding of G does not contain any adjacent 3-faces and adjacent 4-faces, then G is (3,1)*-choosable.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 91-101
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł