Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Fractional (\( \mathcal{P} , \mathcal{Q} \))-Total List Colorings of Graphs

Tytuł:
Fractional (\( \mathcal{P} , \mathcal{Q} \))-Total List Colorings of Graphs
Autorzy:
Kemnitz, Arnfried
Mihók, Peter
Voigt, Margit
Tematy:
graph property
total coloring
(P,Q)-total coloring
fractional coloring
fractional (P,Q)-total chromatic number
circular coloring
circular (P,Q)-total chromatic number
list coloring
(P,Q)-total (a
b)-list colorings
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Język:
angielski
Prawa:
CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 167-179
2083-5892
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
Let $ r, s \in \mathbb{N}$, $r \ge s$, and \( \mathcal{P} \) and \( \mathcal{Q} \) be two additive and hereditary graph properties. A \( (P,Q) \)-total $(r, s)$-coloring of a graph $G = (V,E)$ is a coloring of the vertices and edges of $G$ by $s$-element subsets of $ \mathbb{Z}_r$ such that for each color $i$, $0 \le i \le r − 1$, the vertices colored by subsets containing $i$ induce a subgraph of $G$ with property \( \mathcal{P} \), the edges colored by subsets containing $i$ induce a subgraph of $G$ with property \( \mathcal{Q} \), and color sets of incident vertices and edges are disjoint. The fractional \( (\mathcal{P}, \mathcal{Q})\)-total chromatic number $ \chi_{f,P,Q}^{''}(G)$ of $G$ is defined as the infimum of all ratios $r//s$ such that $G$ has a \( ( \mathcal{P}, \mathcal{Q})\)-total $(r, s)$-coloring. A \( ( \mathcal{P}, \mathcal{Q} \)-total independent set $ T = V_T \cup E_T \subseteq V \cup E$ is the union of a set $V_T$ of vertices and a set $E_T$ of edges of $G$ such that for the graphs induced by the sets $V_T$ and $E_T$ it holds that \( G[ V_T ] \in \mathcal{ P } \), \( G[ E_T ] \in \mathcal{Q} \), and $ G[ V_T ] $ and $ G[ E_T ] $ are disjoint. Let \( T_{ \mathcal{P} , \mathcal{Q} } \) be the set of all \( (\mathcal{P} ,\mathcal{Q})\)-total independent sets of $G$. Let $L(x)$ be a set of admissible colors for every element $ x \in V \cup E $. The graph $G$ is called \( (\mathcal{P} , \mathcal{Q}) \)-total $(a, b)$-list colorable if for each list assignment $L$ with $|L(x)| = a$ for all $x \in V \cup E$ it is possible to choose a subset $ C(x) \subseteq L(x)$ with $|C(x)| = b$ for all $ x \in V \cup E$ such that the set $ T_i $ which is defined by $ T_i = {x \in V \cup E : i \in C(x) } $ belongs to \( T_{ \mathcal{P},\mathcal{Q}}\) for every color $i$. The \( (\mathcal{P}, \mathcal{Q})\)- choice ratio \( \text{chr}_{\mathcal{P},\mathcal{Q}}(G)\) of $G$ is defined as the infimum of all ratios $a//b$ such that $G$ is \( (\mathcal{P},\mathcal{Q})\)-total $(a, b)$-list colorable. We give a direct proof of \( \chi_{ f,\mathcal{P},\mathcal{Q} }^{ \prime \prime } (G) = \text{chr}_{ \mathcal{P} ,\mathcal{Q} }(G)\) for all simple graphs $G$ and we present for some properties \( \mathcal{P} \) and \( \mathcal{Q} \) new bounds for the \( (\mathcal{P}, \mathcal{Q})\)-total chromatic number and for the \((\mathcal{P},\mathcal{Q})\)-choice ratio of a graph $G$.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies