搜索结果: 1-7 共查到“组合数学 coloring”相关记录7条 . 查询时间(0.031 秒)
Acyclic edge-coloring using entropy compression
Acyclic edge-coloring entropy compression Combinatorics
2012/6/29
An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove that every graph with maximum degree Delta has an acyclic edge-co...
We prove that every claw-free graph $G$ that doesn't contain a clique on $\Delta(G) \geq 9$ vertices can be $\Delta(G) - 1$ colored.
Coloring, location and domination of corona graphs
Coloring domination location Roman domination corona graphs
2012/4/18
A vertex coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that every two adjacent vertices of $G$ have different colors. A coloring related property of a graphs is also a...
A proper edge coloring of a graph $G$ is called acyclic if there is no bichromatic cycle in $G$. The acyclic chromatic index of $G$, denoted by $\chi'_a(G)$, is the least number of colors $k$ such tha...
Edge-coloring series-parallel multigraphs
Edge-coloring series-parallel multigraphs Data Structures and Algorithms Combinatorics
2011/10/9
Abstract: We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colore...
The condensation transition in random hypergraph 2-coloring
random structures phase transitions hypergraph 2-coloring second moment method
2011/9/5
Abstract: For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of soluti...
$k$-Conflict-Free Coloring and $k$-Strong-Conflict-Free Coloring for One Class of Hypergraphs and Online $k$-Conflict-Free Coloring
Hypergraphs Online $k$-Conflict-Free Coloring Combinatorics
2011/8/22
Abstract: Conflict-free coloring is a kind of coloring of hypergraphs requiring each hyperedge to have a color which appears only once. More generally, there are $k$-conflict-free coloring ($k$-CF-col...