Zobrazeno 1 - 10
of 15
pro vyhledávání: '"05C15, 05C72"'
Autor:
Steiner, Raphael
Given a graph $G$, its Hall ratio $\rho(G)=\max_{H\subseteq G}\frac{|V(H)|}{\alpha(H)}$ forms a natural lower bound on its fractional chromatic number $\chi_f(G)$. A recent line of research studied the fundamental question of whether $\chi_f(G)$ can
Externí odkaz:
http://arxiv.org/abs/2411.16465
Autor:
Gauci, John Baptist, Zerafa, Jean Paul
Publikováno v:
Art Discrete Appl. Math. 6(1), P1.06 (2023)
A fractional colouring of a graph $G$ is a function that assigns a non-negative real value to all possible colour-classes of $G$ containing any vertex of $G$, such that the sum of these values is at least one for each vertex. The fractional chromatic
Externí odkaz:
http://arxiv.org/abs/2012.11052
Autor:
Mohar, Bojan, Wu, Hehui
Publikováno v:
Combinator. Probab. Comp. 31 (2022) 136-143
It is well known that for any integers $k$ and $g$, there is a graph with chromatic number at least $k$ and girth at least $g$. In 1960's, Erd\H{o}s and Hajnal conjectured that for any $k$ and $g$, there exists a number $h(k,g)$, such that every grap
Externí odkaz:
http://arxiv.org/abs/1808.01605
Autor:
Chen, Guantao, Jing, Guangming
Appearing in different format, Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that if $G$ is an edge-$k$-critical graph with $k \ge \Delta +1$, then $|V(G)|$ is odd and, for every edge $e$, $E(G-e)$ is a union of d
Externí odkaz:
http://arxiv.org/abs/1709.04568
We conjecture that any graph $G$ with treewidth~$k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. We also show that any graph $G$ with treewidth~$k\geq 4$
Externí odkaz:
http://arxiv.org/abs/1603.05018
Autor:
Cranston, Daniel W., Rabern, Landon
Publikováno v:
Combinatorica. Vol. 37(5), October 2017, pp. 837-861
The chromatic number of the plane is the chromatic number of the uncountably infinite graph that has as its vertices the points of the plane and has an edge between two points if their distance is 1. This chromatic number is denoted $\chi(\mathcal{R}
Externí odkaz:
http://arxiv.org/abs/1501.01647
We prove that every subcubic triangle-free graph has fractional chromatic number at most 14/5, thus confirming a conjecture of Heckman and Thomas [A new proof of the independence ratio of triangle-free cubic graphs. Discrete Math. 233 (2001), 233--23
Externí odkaz:
http://arxiv.org/abs/1301.5296
Heckman and Thomas conjectured that the fractional chromatic number of any triangle-free subcubic graph is at most 14/5. Improving on estimates of Hatami and Zhu and of Lu and Peng, we prove that the fractional chromatic number of any triangle-free s
Externí odkaz:
http://arxiv.org/abs/1203.1308
Autor:
John Baptist Gauci, Jean Paul Zerafa
A fractional colouring of a graph $G$ is a function that assigns a non-negative real value to all possible colour-classes of $G$ containing any vertex of $G$, such that the sum of these values is at least one for each vertex. The fractional chromatic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e63a413908c47a41884be5276f3ed78f
http://arxiv.org/abs/2012.11052
http://arxiv.org/abs/2012.11052
Autor:
Hehui Wu, Bojan Mohar
Publikováno v:
Electronic Notes in Discrete Mathematics. 49:661-666
It is well known that for any integers $k$ and $g$, there is a graph with chromatic number at least $k$ and girth at least $g$. In 1960's, Erd\H{o}s and Hajnal conjectured that for any $k$ and $g$, there exists a number $h(k,g)$, such that every grap
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c31ff508b4c24ca87d06b9f34daf48c0
https://doi.org/10.1016/j.endm.2015.06.089
https://doi.org/10.1016/j.endm.2015.06.089
