Zobrazeno 1 - 10
of 123
pro vyhledávání: '"Kardoš, František"'
We consider the robust chromatic number $\chi_1(G)$ of planar graphs $G$ and show that there exists an infinite family of planar graphs $G$ with $\chi_1(G) = 3$, thus solving a recent problem of Bacs\'{o}~et~al. (The robust chromatic number of graphs
Externí odkaz:
http://arxiv.org/abs/2401.08324
Let $G$ be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the $S_4$-Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of $G$ such that the complement of their union is a bipartite subg
Externí odkaz:
http://arxiv.org/abs/2309.06944
Publikováno v:
J. Combin. Theory Ser. B 160, 1--14 (2023). Share Link: https://authors.elsevier.com/a/1gKfKLpTmV29P
Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two othe
Externí odkaz:
http://arxiv.org/abs/2204.10021
Autor:
Deschamps, Quentin, Feghali, Carl, Kardoš, František, Legrand-Duchesne, Clément, Pierron, Théo
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and~$\beta$ whenever the coloring~$\beta$ can be obtained from $\alpha$ by a
Externí odkaz:
http://arxiv.org/abs/2201.07595
We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen from 1974.
Comment: 7 pages plus 6 pages of annex; 11 figures
Comment: 7 pages plus 6 pages of annex; 11 figures
Externí odkaz:
http://arxiv.org/abs/2108.06115
A circular $r$-coloring of a signed graph $(G, \sigma)$ is an assignment $\phi$ of points of a circle $C_r$ of circumference $r$ to the vertices of $(G, \sigma)$ such that for each positive edge $uv$ of $(G, \sigma)$ the distance of $\phi(v)$ and $\p
Externí odkaz:
http://arxiv.org/abs/2107.12126
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the follo
Externí odkaz:
http://arxiv.org/abs/2009.12189
A fullerene graph is a 3-connected cubic planar graph with pentagonal and hexagonal faces. The leapfrog transformation of a planar graph produces the trucation of the dual of the given graph. A fullerene graph is leapfrog if it can be obtained from a
Externí odkaz:
http://arxiv.org/abs/1910.03992
Autor:
Kardoš, František, Narboni, Jonathan
There are several ways to generalize graph coloring to signed graphs. M\'a\v{c}ajov\'a, Raspaud and \v{S}koviera introduced one of them and conjectured that in this setting, for signed planar graphs four colors are always enough, generalising thereby
Externí odkaz:
http://arxiv.org/abs/1906.05638
Publikováno v:
In Journal of Combinatorial Theory, Series B May 2023 160:1-14
