Results 11 to 20 of about 115,444 (312)
Some Conclusion on Unique k-List Colorable Complete Multipartite Graphs
Journal of Applied Mathematics, 2013 If a graph G admits a k-list assignment L such that G has a unique L-coloring, then G is called uniquely k-list colorable graph, or UkLC graph for short.
Yanning Wang, Yanyan Wang, Xuguang Zhang
doaj +7 more sources
Total Equitable List Coloring [PDF]
Graphs and Combinatorics, 2018 An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. A graph $G$ is equitably $k$-colorable if there exists an equitable coloring of $G$ which uses $k$ colors, each one appearing on either $\lfloor |V(G)|/k \rfloor$ or $\lceil |V(G)|/k \rceil$ vertices of $G$. In 1994, Fu conjectured that
Hemanshu Kaul +2 more
+8 more sources
List Coloring Triangle-Free Hypergraphs [PDF]
Random Structures & Algorithms, 2013 A triangle in a hypergraph is a collection of distinct vertices u,v,w and distinct edges e,f,g with u,v \in e, v,w \in f, w,u \in g, and \{u,v,w\} \cap e \cap f \cap g=\emptyset. The i-degree of a vertex in a hypergraph is the number of edges of size i containing it.
Jeff Cooper, Dhruv Mubayi
openalex +4 more sources
Parameterized Pre-Coloring Extension and List Coloring Problems [PDF]
SIAM Journal on Discrete Mathematics, 2021 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 clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $v\in V(G)$, decide whether $
Gregory Gutin +3 more
openaire +7 more sources
Random Structures & Algorithms, 2023 AbstractList coloring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list‐coloring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a ‐list‐assignment of a graph ,
Stijn Cambie +3 more
openaire +7 more sources
Kempe Equivalent List Colorings
Combinatorica, 2023 29 pages, 12 figures; second version extends the main result to cliques, which were previously excluded; third version incorporates reviewer feedback; to appear in ...
Cranston, Daniel W., Mahmoud, Reem
openaire +3 more sources
List Coloring Hypergraphs [PDF]
The Electronic Journal of Combinatorics, 2010 Let $H$ be a hypergraph and let $L_v : v \in V(H)$ be sets; we refer to these sets as lists and their elements as colors. A list coloring of $H$ is an assignment of a color from $L_v$ to each $v \in V(H)$ in such a way that every edge of $H$ contains a pair of vertices of different colors.
Haxell, Penny, Verstraete, Jacques
openaire +2 more sources
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
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