Results 1 to 10 of about 14,237 (338)
Parameterized Pre-Coloring Extension and List Coloring Problems [PDF]
SIAM Journal on Discrete Mathematics, 2020 Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a ...
Ordyniak, Sebastian +11 more
core +9 more sources
Parameterized Complexity of List Coloring and Max Coloring
, 2022 In the List Coloring problem, the input is a graph G and list of colors L: V(G) → N for each vertex v∈ V(G). The objective is to test the existence of a coloring λ: V(G) → N such that for each v∈ V(G), λ(v) ∈ L(v) and for each edge (u, v) ∈ E(G), λ(u ...
Aryanfard, Bardiya, Panolan, Fahad
core +2 more sources
Discussiones Mathematicae Graph Theory, 2023 DP-coloring is generalized via relaxed coloring and variable degeneracy in [P. Sittitrai and K. Nakprasit, Su cient conditions on planar graphs to have a relaxed DP-3-coloring, Graphs Combin. 35 (2019) 837–845], [K.M. Nakprasit and K.
Sribunhung Sarawute +3 more
doaj +1 more source
A Grover Search-Based Algorithm for the List Coloring Problem
IEEE Transactions on Quantum Engineering, 2022 Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for $k$-coloring of graphs on $n$ vertices has runtimes $\Omega (2^n)$ for $k\geq 5$.
Sayan Mukherjee
doaj +1 more source
Uniquely list colorability of the graph Kn^2 + Om
Selecciones Matemáticas, 2020 Given a list L(v) for each vertex v, we say that the graph G is L-colorable if there is a proper vertex coloring of G where each vertex v takes its color from L(v). The graph is uniquely k-list colorable if there is a list assignment L such that jL(v)j =
Le Xuan Hung
doaj +1 more source
Linear choosability of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A proper vertex coloring of a non oriented graph $G=(V,E)$ is linear if the graph induced by the vertices of two color classes is a forest of paths. A graph $G$ is $L$-list colorable if for a given list assignment $L=\{L(v): v∈V\}$, there exists a proper
Louis Esperet +2 more
doaj +1 more source
The List Edge Coloring and List Total Coloring of Planar Graphs with Maximum Degree at Least 7
Discussiones Mathematicae Graph Theory, 2020 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 ...
Sun Lin +3 more
doaj +1 more source
A Note on the Equitable Choosability of Complete Bipartite Graphs
Discussiones Mathematicae Graph Theory, 2021 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 ...
Mudrock Jeffrey A. +4 more
doaj +1 more source
AKCE International Journal of Graphs and Combinatorics, 2023 We introduce a concept in graph coloring motivated by the popular Sudoku puzzle. Let [Formula: see text] be a graph of order n with chromatic number [Formula: see text] and let [Formula: see text] Let [Formula: see text] be a k-coloring of the induced ...
J. Maria Jeyaseeli +3 more
doaj +1 more source
Edge-group choosability of outerplanar and near-outerplanar graphs [PDF]
Transactions on Combinatorics, 2020 Let $\chi_{gl}(G)$ be the {\it{group choice number}} of $G$. A graph $G$ is called {\it{edge-$k$-group choosable}} if its line graph is $k$-group choosable. The {\it{group-choice index}} of $G$, $\chi'_{gl}(G)$, is the smallest $k$ such that $G$ is edge-$
Amir Khamseh
doaj +1 more source