Temat: equitable graph coloring

Skocz do pozycji: 1.

Tytuł:: Equitable Colorings Of Corona Multiproducts Of Graphs
Autorzy:: Furmánczyk, Hanna
Kubale, Marek
Mkrtchyan, Vahan V.
Tematy:: corona graph
equitable chromatic number
equitable coloring conjecture
equitable graph coloring
multiproduct of graphs
NP-completeness
polynomial algorithm; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341573.pdf Link otwiera się w nowym oknie
Opis:: A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ₌(G). It is known that the problem of computation of χ₌(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦^l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: On List Equitable Total Colorings of the Generalized Theta Graph
Autorzy:: Mudrock, Jeffrey A.
Marsh, Max
Wagstrom, Tim
Tematy:: graph coloring
total coloring
equitable coloring
list coloring
equitable choosability; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32326107.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: A Note on the Equitable Choosability of Complete Bipartite Graphs
Autorzy:: Mudrock, Jeffrey A.
Chase, Madelynn
Thornburgh, Ezekiel
Kadera, Isaac
Wagstrom, Tim
Tematy:: graph coloring
equitable coloring
list coloring
equitable choos-ability; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32325306.pdf Link otwiera się w nowym oknie
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 said to be equitably k-choosable if an equitable L-coloring of G exists whenever L is a k-assignment for G. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies K_n,m is equitably k-choosable if k ≥ max{n, m} provided K_n,m ≠ K_2l+1,2l+1. We prove K_n,m is equitably k-choosable if m ≤ ⌈ (m + n)/k⌉ (k − n) which gives Kn,m is equitably k-choosable for certain k satisfying k < max{n, m}. We also give a complete characterization of the equitable choosability of complete bipartite graphs that have a partite set of size at most 2.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Equitable coloring of graph products
Autorzy:: Furmańczyk, H.
Tematy:: equitable coloring
graph product; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/254911.pdf Link otwiera się w nowym oknie
Opis:: A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the "equitable chromatic number" of G and denoted by χ=(G). It is interesting to note that if a graph G is equitably k-colorable, it does not imply that it is equitably (k + 1)-colorable. The smallest integer k for which G is equitably k'-colorable for all k' ≥ k is called "the equitable chromatic threshold" of G and denoted by χ*=(G). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [2] for Cartesian, weak and strong tensor products.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Autorzy:: Furmańczyk, H.
Kubale, M.
Tematy:: batch scheduling
equitable coloring
semi-equitable coloring
cubic graph; Pokaż więcej
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Powiązania:: https://bibliotekanauki.pl/articles/230004.pdf Link otwiera się w nowym oknie
Opis:: In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Equitable coloring of Kneser graphs
Autorzy:: Fidytek, Robert
Furmańczyk, Hanna
Żyliński, Paweł
Tematy:: equitable coloring
Kneser graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743125.pdf Link otwiera się w nowym oknie
Opis:: The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k) are discussed.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
Autorzy:: Dong, Aijun
Zhang, Xin
Tematy:: graph coloring
equitable choosability
maximum average degree; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342275.pdf Link otwiera się w nowym oknie
Opis:: A graph is said to be equitably $k$-colorable if the vertex set $V (G)$ can be partitioned into $k$ independent subsets $ V_1, V_2, . . ., V_k $ such that $ | | V_i |−| V_j | | \le 1 $ $(1 \le i, j \le k) $. A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $ \ceil{ \frac{|V(G)|}{ k } } $ vertices. In this paper, we prove that if $G$ is a graph such that $ mad(G) < 3 $, then $G$ is equitably $k$-colorable and equitably $k$- choosable where $ k \ge \text{max} \{ \Delta (G), 4 \} $. Moreover, if $G$ is a graph such that $ mad(G) < \frac{12}{5} $, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $ k \ge \text{max} \{ \Delta (G), 3 \} $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: An improved bound on the chromatic number of the Pancake graphs
Autorzy:: Droogendijk, Leen
Konstantinova, Elena
Tematy:: Pancake graph
chromatic number
equitable coloring; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59882303.pdf Link otwiera się w nowym oknie
Opis:: In this paper, an improved bound on the chromatic number of the Pancake graph $ P_n, n\geqslant 9 $, is presented. The bound is obtained using a subadditivity property of the chromatic number of the Pancake graph. We also investigate an equitable coloring of $P_n$. An equitable $(n-1)$-coloring based on efficient dominating sets is given and optimal equitable $4$-colorings are considered for small $n$. It is conjectured that the chromatic number of $P_n$ coincides with its equitable chromatic number for any $ n \geqslant 2 $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Equitable choosability of prism graphs
Autorzy:: Hogenson, Kirsten
Johnston, Dan
O'Hara, Suzanne
Tematy:: list coloring
equitable list coloring
prism graph
reducible configuration
discharging; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59945824.pdf Link otwiera się w nowym oknie
Opis:: A graph $G$ is equitably $k$-choosable if, for every $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $\ceil{ |V(G)|//k}$ vertices. Equitable list-coloring was introduced by Kostochka, Pelsmajer, and West in 2003 [A list analogue of equitable coloring, J. Graph Theory 44 (2003) 166–177]. They conjectured that a connected graph $G$ with $\Delta(G)\geq 3$ is equitably $\Delta(G)$-choosable, as long as $G$ is not complete or $K_{d,d}$ for odd $d$. In this paper, we use a discharging argument to prove their conjecture for the infinite family of prism graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Autorzy:: Furmańczyk, H.
Jastrzębski, A.
Kubale, M.
Tematy:: computer experiments
corona graph
equitable chromatic number
equitable coloring conjectures
NP-hardness
polynomial heuristics; Pokaż więcej
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Powiązania:: https://bibliotekanauki.pl/articles/230069.pdf Link otwiera się w nowym oknie
Opis:: In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "equitable graph coloring" wg kryterium: Temat