搜索结果: 1-8 共查到“数学 the Chromatic Number”相关记录8条 . 查询时间(0.062 秒)
On incompactness for chromatic number of graphs
set theory graphs chromatic number compactness non-reflecting stationary sets
2012/5/9
We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality kappa . We prove that one can define a graph G whose chromatic number is > kappa, while the chromatic nu...
Grid Representations and the Chromatic Number
Grid Representations the Chromatic Number Combinatorics
2012/4/17
A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points that some line segme...
Large cliques in graphs with high chromatic number
Large cliques high chromatic number graphs Combinatorics
2011/9/5
Abstract: We study graphs whose chromatic number is close to the order of the graph (the number of vertices). Both when the chromatic number is a constant multiple of the order and when the difference...
Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz
Chromatic number clique subdivisions Hajos and Erdos-Fajtlowicz Combinatorics
2011/9/1
Abstract: For a graph $G$, let $\chi(G)$ denote its chromatic number and $\sigma(G)$ denote the order of the largest clique subdivision in $G$. Let H(n) be the maximum of $\chi(G)/\sigma(G)$ over all ...
About maximal number of edges in hypergraph-clique with chromatic number 3
hypergraph-clique chromatic number 3 Combinatorics
2011/8/31
Abstract: Let $ H = (V,E) $ be a hypergraph. By the chromatic number of a hypergraph $ H = (V,E) $ we mean the minimum number $\chi(H)$ of colors needed to paint all the vertices in $ V $ so that any ...
The Fractional Chromatic Number of Triangle-free Graphs with $\Delta\leq 3$
Triangle-free Graphs Combinatorics
2010/11/18
Let $G$ be any triangle-free graph with maximum degree $\Delta\leq 3$. Staton proved that the independence number of $G$ is at least $\frac{5}{14}n$. Heckman and Thomas conjectured that Staton's resul...
The adjacent vertex distinguishing total chromatic number
The adjacent vertex distinguishing total chromatic number
2010/12/2
A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive di erent col...
Let G be a planar graph with δ(G)≥3, fo be a face of G. In this paper it is proved that for any Halin graph with △(G)≥6, X (G)＝△(G)+1, where △(G), Xo (G) denote the maximum degree and the complete chr...