Informacja

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

Wyszukujesz frazę "total-coloring" wg kryterium: Temat


Tytuł:
Equitable Total Coloring of Corona of Cubic Graphs
Autorzy:
Furmańczyk, Hanna
Zuazua, Rita
Powiązania:
https://bibliotekanauki.pl/articles/32361758.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
equitable coloring
total coloring
equitable total coloring
cubic graphs
Opis:
The minimum number of total independent partition sets of V∪E of a graph G = (V, E) is called the total chromatic number of G, denoted by χ'′(G). If the difference between cardinalities of any two total independent sets is at most one, then the minimum number of total independent partition sets of V∪E is called the equitable total chromatic number, and is denoted by χ'′=(G). In this paper we consider equitable total coloring of coronas of cubic graphs, G◦H. It turns out that independently on the values of equitable total chromatic number of factors G and H, equitable total chromatic number of corona G◦H is equal to Δ(G◦H)+1. Thereby, we confirm Total Coloring Conjecture (TCC), posed by Behzad in 1964, and Equitable Total Coloring Conjecture (ETCC), posed by Wang in 2002, for coronas of cubic graphs. As a direct consequence we get that all coronas of cubic graphs are of Type 1.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1147-1163
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Coloring of Claw-Free Planar Graphs
Autorzy:
Liang, Zuosong
Powiązania:
https://bibliotekanauki.pl/articles/32304195.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total coloring
total coloring conjecture
planar graph
claw
Opis:
A total coloring of a graph is an assignment of colors to both its vertices and edges so that adjacent or incident elements acquire distinct colors. Let Δ(G) be the maximum degree of G. Vizing conjectured that every graph has a total (Δ + 2)-coloring. This Total Coloring Conjecture remains open even for planar graphs, for which the only open case is Δ = 6. Claw-free planar graphs have Δ ≤ 6. In this paper, we prove that the Total Coloring Conjecture holds for claw-free planar graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 771-777
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized Fractional Total Colorings of Complete Graph
Autorzy:
Karafová, Gabriela
Powiązania:
https://bibliotekanauki.pl/articles/30145422.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
fractional coloring
total coloring
complete graphs
Opis:
An additive and hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let $P$ and $Q$ be two additive and hereditary graph properties and let $r,s$ be integers such that $r\geq s$. Then an $\frac{r}{s}$-fractional $(P,Q)$-total coloring of a finite graph $G=(V,E)$ is a mapping $f$, which assigns an $s$-element subset of the set $\{1,2,...,r\}$ to each vertex and each edge, moreover, for any color $i$ all vertices of color $i$ induce a subgraph of property $P$, all edges of color $i$ induce a subgraph of property $Q$ and vertices and incident edges have assigned disjoint sets of colors. The minimum ratio $\frac{r}{s}$ of an $\frac{r}{s}$-fractional $(P,Q)$-total coloring of $G$ is called fractional $(P,Q)$-total chromatic number $\chi_{f,P,Q}^{''}(G)=\frac{r}{s}$. Let $k=$ sup$\{i:K_{i+1}\in P\}$ and $l=$ sup$\{i:K_{i+1}\in Q\}$. We show for a complete graph $K_{n}$ that if $l\geq k+2$ then $\chi_{f,P,Q}^{''}(K_{n})=\frac{n}{k+1}$ for a sufficiently large $n$.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 665-676
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized Fractional Total Colorings of Graphs
Autorzy:
Karafová, Gabriela
Soták, Roman
Powiązania:
https://bibliotekanauki.pl/articles/31339383.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
fractional coloring
total coloring
automorphism group
Opis:
Let \( \mathcal{P} \) and \( \mathcal{Q} \) be additive and hereditary graph properties and let $r$, $s$ be integers such that $ r \ge s $. Then an $ r/s$-fractional (\( \mathcal{P} \),\( \mathcal{Q} \))-total coloring of a finite graph $ G = (V, E) $ is a mapping $f$, which assigns an $s$-element subset of the set $ {1, 2, . . ., r}$ to each vertex and each edge, moreover, for any color $i$ all vertices of color $i$ induce a subgraph with property \( \mathcal{P} \), all edges of color $i$ induce a subgraph with property \( \mathcal{Q} \) and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an \( \frac{r}{s} \)-fractional (\( \mathcal{P} \),\( \mathcal{Q} \))-total coloring of G is called fractional (\( \mathcal{P} \), \( \mathcal{Q} \))-total chromatic number \( \chi_{f, \mathcal{P} ,\mathcal{Q} }^{ \prime \prime } (G) = \frac{r}{s} \). We show in this paper that \( \chi_{f, \mathcal{P} ,\mathcal{Q} }^{ \prime \prime } \) of a graph \( G \) with \( o(V (G)) \) vertex orbits and \( o(E(G)) \) edge orbits can be found as a solution of a linear program with integer coefficients which consists only of \( o(V (G)) + o(E(G)) \) inequalities.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 463-473
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a Total Version of 1-2-3 Conjecture
Autorzy:
Baudon, Olivier
Hocquard, Hervé
Marczyk, Antoni
Pilśniak, Monika
Przybyło, Jakub
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/31348090.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
neighbor sum distinguishing total coloring
general edge coloring
total coloring
neighbor-distinguishing index
neighbor full sum distinguishing total k -coloring
Opis:
A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set {1, . . ., k}. These colors can be used to distinguish adjacent vertices of G. There are many possibilities of such a distinction. In this paper, we focus on the one by the full sum of colors of a vertex, i.e., the sum of the color of the vertex, the colors on its incident edges and the colors on its adjacent vertices. This way of distinguishing vertices has similar properties to the method when we only use incident edge colors and to the corresponding 1-2-3 Conjecture.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1175-1186
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Zig-zag facial total-coloring of plane graphs
Autorzy:
Czap, J.
Jendrol, S.
Voigt, M.
Powiązania:
https://bibliotekanauki.pl/articles/255827.pdf
Data publikacji:
2018
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
plane graph
facial coloring total-coloring zig-zag coloring
Opis:
In this paper we introduce the concept of zig-zag facial total-coloring of plane graphs. We obtain lower and upper bounds for the minimum number of colors which is necessary for such a coloring. Moreover, we give several sharpness examples and formulate some open problems.
Źródło:
Opuscula Mathematica; 2018, 38, 6; 819-827
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles
Autorzy:
Wang, Bing
Wu, Jian-Liang
Sun, Lin
Powiązania:
https://bibliotekanauki.pl/articles/31342246.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total coloring
embedded graph
cycle
Opis:
A total-k-coloring of a graph G is a coloring of V ∪ E using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ′′(G) of G is the smallest integer k such that G has a total-k-coloring. Let G be a graph embedded in a surface of Euler characteristic ε ≥ 0. If G contains no 3-cycles adjacent to 4-cycles, that is, no 3-cycle has a common edge with a 4-cycle, then χ′′(G) ≤ max{8, Δ+1}.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 977-989
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on total colorings of planar graphs without 4-cycles
Autorzy:
Wang, Ping
Wu, Jian-Liang
Powiązania:
https://bibliotekanauki.pl/articles/744436.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total coloring
planar graph
list coloring
girth
Opis:
Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 125-135
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
Autorzy:
Cranston, Daniel
Powiązania:
https://bibliotekanauki.pl/articles/743133.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
list coloring
edge coloring
total coloring
Vizing's Conjecture
Opis:
Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if G is a planar graph with no two 3-cycles sharing an edge and with Δ(G) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u)+d(v) ≤ Δ(G)+2. All of our proofs yield linear-time algorithms that produce the desired colorings.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 163-178
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs Km,N(m < n)
Autorzy:
Chen, Xiang’en
Gao, Yuping
Yao, Bing
Powiązania:
https://bibliotekanauki.pl/articles/30146641.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
complete bipartite graphs
IE-total coloring
vertex-distinguishing IE-total coloring
vertex-distinguishing IE-total chromatic number
Opis:
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs Km,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of Km,n(1 ≤ m ≤ 7, m < n) as well as complete graphs Kn are obtained.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 289-306
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten
Autorzy:
Dong, Aijun
Li, Tong
Powiązania:
https://bibliotekanauki.pl/articles/32227944.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total coloring
neighbor product distinguishing coloring
planar graph
Opis:
A proper [k]-total coloring c of a graph G is a proper total coloring c of G using colors of the set [k] = {1, 2, . . ., k}. Let p(u) denote the product of the color on a vertex u and colors on all the edges incident with u. For each edge uv ∈ E(G), if p(u) ≠ p(v), then we say the coloring c distinguishes adjacent vertices by product and call it a neighbor product distinguishing k-total coloring of G. By X(G), we denote the smallest value of k in such a coloring of G. It has been conjectured by Li et al. that Δ(G) + 3 colors enable the existence of a neighbor product distinguishing total coloring. In this paper, by applying the Combinatorial Nullstellensatz, we obtain that the conjecture holds for planar graph with Δ(G) ≥ 10. Moreover, for planar graph G with Δ(G) ≥ 11, it is neighbor product distinguishing (Δ(G) + 2)-total colorable, and the upper bound Δ(G) + 2 is tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 981-999
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The List Edge Coloring and List Total Coloring of Planar Graphs with Maximum Degree at Least 7
Autorzy:
Sun, Lin
Wu, Jianliang
Wang, Bing
Liu, Bin
Powiązania:
https://bibliotekanauki.pl/articles/31348158.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
list edge coloring
list total coloring
Opis:
A graph $G$ is edge $k$-choosable (respectively, total $k$-choosable) if, whenever we are given a list $L(x)$ of colors with $|L(x)| = k$ for each $x ∈ E(G) (x ∈ E(G) ∪ V (G))$, we can choose a color from $L(x)$ for each element $x$ such that no two adjacent (or incident) elements receive the same color. The list edge chromatic index $χ_l^′(G)$ (respectively, the list total chromatic number $χ_l^{′′}(G))$ of $G$ is the smallest integer $k$ such that $G$ is edge (respectively, total) $k$-choosable. In this paper, we focus on a planar graph $G$, with maximum degree $Δ (G) ≥ 7$ and with some structural restrictions, satisfies $χ_l^′(G) = Δ (G)$ and $χ_l^{′′}(G) = Δ (G) + 1$.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1005-1024
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On List Equitable Total Colorings of the Generalized Theta Graph
Autorzy:
Mudrock, Jeffrey A.
Marsh, Max
Wagstrom, Tim
Powiązania:
https://bibliotekanauki.pl/articles/32326107.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
total coloring
equitable coloring
list coloring
equitable choosability
Opis:
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph G assigns a list, L(v), of k available colors to each v ∈ V (G), and an equitable L-coloring of G is a proper coloring, f, of G such that f(v) ∈ L(v) for each v ∈ V (G) and each color class of f has size at most ⌈|V (G)|/k⌉. Graph G is equitably k-choosable if G is equitably L-colorable whenever L is a k-assignment for G. In 2018, Kaul, Mudrock, and Pelsmajer subsequently introduced the List Equitable Total Coloring Conjecture which states that if T is a total graph of some simple graph, then T is equitably k-choosable for each k ≥ max{x(T), Δ(T)/2 + 2} where Δ(T) is the maximum degree of a vertex in T and x(T ) is the list chromatic number of T. In this paper, we verify the List Equitable Total Coloring Conjecture for subdivisions of stars and the generalized theta graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1215-1233
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Facial [r,s,t]-Colorings of Plane Graphs
Autorzy:
Czap, Július
Šugerek, Peter
Jendrol’, Stanislav
Valiska, Juraj
Powiązania:
https://bibliotekanauki.pl/articles/31343366.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
plane graph
boundary walk
edge-coloring
vertex-coloring
total-coloring
Opis:
Let $G$ be a plane graph. Two edges are facially adjacent in $G$ if they are consecutive edges on the boundary walk of a face of $G$. Given nonnegative integers $r$, $s$, and $t$, a facial $[r, s, t]$-coloring of a plane graph $G = (V,E)$ is a mapping $f : V \cup E \rightarrow {1, . . ., k} $ such that $ |f(v_1) − f(v_2)| \ge r $ for every two adjacent vertices $ v_1 $ and $ v_2 $, $ | f(e_1) − f(e_2)| \ge s $ for every two facially adjacent edges $ e_1 $ and $ e_2 $, and $ | f(v) − f(e)| \ge t $ for all pairs of incident vertices $ v $ and edges $ e $. The facial $[r, s, t]$-chromatic number $ \overline{ \chi }_{r,s,t} (G) $ of $ G $ is defined to be the minimum $k$ such that $G$ admits a facial $[r, s, t]$-coloring with colors $1, . . ., k$. In this paper we show that $ \overline{ \chi }_{r,s,t} (G) \le 3r + 3s + t + 1 $ for every plane graph $G$. For some triplets $ [r, s, t] $ and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters $r$, $s$, and $t$ are small.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 629-645
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An Improved Upper Bound on Neighbor Expanded Sum Distinguishing Index
Autorzy:
Vučković, Bojan
Powiązania:
https://bibliotekanauki.pl/articles/32083737.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
general edge coloring
total coloring
neighbor sum distinguishing index
Opis:
A total k-weighting f of a graph G is an assignment of integers from the set {1, . . ., k} to the vertices and edges of G. We say that f is neighbor expanded sum distinguishing, or NESD for short, if Σw∈N(v) (f(vw) + f(w)) differs from Σw∈N(u)(f(uw) + f(w)) for every two adjacent vertices v and u of G. The neighbor expanded sum distinguishing index of G, denoted by egndiΣ(G), is the minimum positive integer k for which there exists an NESD weighting of G. An NESD weighting was introduced and investigated by Flandrin et al. (2017), where they conjectured that egndiΣ(G) ≤ 2 for any graph G. They examined some special classes of graphs, while proving that egndiΣ(G) ≤ χ(G) + 1. We improve this bound and show that egndiΣ(G) ≤ 3 for any graph G. We also show that the conjecture holds for all bipartite, 3-regular and 4-regular graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 323-329
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł

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