Results 11 to 20 of about 700 (120)
On incidence coloring of graph fractional powers [PDF]
Opuscula Mathematica, 2022 For any \(n\in \mathbb{N}\), the \(n\)-subdivision of a graph \(G\) is a simple graph \(G^\frac{1}{n}\) which is constructed by replacing each edge of \(G\) with a path of length \(n\). The \(m\)-th power of \(G\) is a graph, denoted by \(G^m\), with the
Mahsa Mozafari-Nia, Moharram N. Iradmusa
doaj +1 more source
On the density of sets of the Euclidean plane avoiding distance 1 [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forall x,y \in A, \left\| x-y \right\|_2 \neq 1.$ In this paper we study the number $m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurable sets avoiding distance ...
Thomas Bellitto +2 more
doaj +1 more source
Fractional Chromatic Number, Maximum Degree, and Girth [PDF]
SIAM Journal on Discrete Mathematics, 2021 We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$Δ\ge 3$.
Pirot, François +1 more
openaire +4 more sources
Cubical coloring — fractional covering by cuts and semidefinite programming [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings.
Robert Šámal
doaj +1 more source
New eigenvalue bound for the fractional chromatic number
Journal of Graph Theory, 2023 AbstractGiven a graph , we let denote the sum of the squares of the positive eigenvalues of the adjacency matrix of , and we similarly define . We prove that and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number .
Krystal Guo, Sam Spiro
openaire +5 more sources
Discussiones Mathematicae Graph Theory, 2022 We introduce a new notion of circular colourings for digraphs. The idea of this quantity, called star dichromatic number χ→*\vec \chi * (D) of a digraph D, is to allow a finer subdivision of digraphs with the same dichromatic number into such which are ...
Hochstättler Winfried, Steiner Raphael
doaj +1 more source
1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio [PDF]
Combinatorica, 2020 The Hall ratio of a graph \(G\) is given by \(\max \frac{\left\vert V(H)\right\vert}{\alpha (H)},\) where \(\alpha (G)\) is the independence number of \(G,\) and the maximum is taken over all subgraphs \(H\) of \(G.\) It is well known that the \ Hall ratio provides a lower bound for the fractional chromatic number.
Ossona de Mendez, Patrice +3 more
openaire +3 more sources
Choosability and fractional chromatic numbers
Discrete Mathematics, 1997 Let \(G=(V,E)\) be a graph. The problem of finding its chromatic number, \(\chi(G)\), can be formulated as an integer linear program: \[ \text{minimize}\quad \sum_{S\in{\mathcal S}(G)}\phi(S),\quad\text{over all }\phi\in{\mathcal P}(G); \] \[ \text{subject to}\quad\sum_{\phi\in S\in{\mathcal S}(G)}\phi(S)\geq 1,\quad\text{for all }\nu\in V, \] where \({
Noga Alon, Zsolt Tuza, Margit Voigt
openaire +1 more source
Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs
European Journal of Combinatorics, 1998 This paper studies the circular (or star) chromatic numbers and fractional chromatic numbers of distance graphs \(G(Z, D)\) for various sets \(D\) (being the graph with vertex set a subset of the integers, and two vertices \(x\), \(y\) being adjacent iff \(| x-y|\in D\)). Various specific cases are calculated, including all cases when \(| D|= 2\).
Chang, Gerard J. +2 more
openaire +2 more sources
Scheduling N Burgers for a k-Burger Grill: Chromatic Numbers With Restrictions
Theory and Applications of Graphs, 2015 The chromatic number has a well-known interpretation in the area of scheduling. If the vertices of a finite, simple graph are committees, and adjacency of two committees indicates that they must never be in session simultaneously, then the chromatic ...
Peter Johnson, Xiaoya Zha
doaj +1 more source