- Tytuł:
- Linear List Coloring of Some Sparse Graphs
- Autorzy:
-
Chen, Ming
Li, Yusheng
Zhang, Li - Powiązania:
- https://bibliotekanauki.pl/articles/32083756.pdf
- Data publikacji:
- 2021-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
linear coloring
maximum average degree
planar graphs
discharging - Opis:
- A linear $k$-coloring of a graph is a proper $k$-coloring of the graph such that any subgraph induced by the vertices of any pair of color classes is a union of vertex-disjoint paths. A graph $G$ is linearly $L$-colorable if there is a linear coloring $c$ of $G$ for a given list assignment $L = \{L(v) : v ∈ V(G)\}$ such that $c(v) ∈ L(v)$ for all $v ∈ V(G)$, and $G$ is linearly $k$-choosable if $G$ is linearly $L$-colorable for any list assignment with $|L(v)| ≥ k$. The smallest integer $k$ such that $G$ is linearly $k$-choosable is called the linear list chromatic number, denoted by $lc_l(G)$. It is clear that \(lc_l(G)≥\Big\lceil\frac{\Delta(G)}{1}\Big\rceil+1\) for any graph $G$ with maximum degree $\Delta(G)$. The maximum average degree of a graph $G$, denoted by $mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. In this note, we shall prove the following. Let $G$ be a graph, (1) if $mad(G)<\frac{8}{3}$ and $\Delta(G) ≥ 7$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (2) if $mad(G)<{18}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)=\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+1\); (3) if $mad(G)<{20}{7}$ and $\Delta(G) ≥ 5$, then \(lc_l(G)≤\Big\lceil\frac{\Delta(G)}{2}\Big\rceil+2\).
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 51-64
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł