Filters
Graphs with bounded tree-width and large odd-girth are almost bipartite
We prove that every graph with bounded tree-width without short odd cycles has circular chromatic number arbitrarily close to two.
BA - Obecná matematika
- 2010 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Girth, oddness, and colouring defect of snarks
-edge-connected snarks with oddness 2 and arbitrarily large girth. The fact that our snarks (cubic graphs with no 3-edge-colouring) of oddness 2 and arbitrarily large of snarks with large girt...
Pure mathematics
- 2022 •
- Jimp •
- Link
Rok uplatnění
Jimp - Článek v periodiku v databázi Web of Science
Výsledek na webu
Planar graphs of odd-girth at least 9 are homomorphic to the Petersen graph
to the Petersen graph. The {em odd-girth} of a graph $G$ is the length of the shortest odd cycle in $G$ ($infty$ if $G$ is bipartite). We prove that every planar graph of odd-girth atleast $9$ is $(5,2)$-...
BA - Obecná matematika
- 2008 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Vertex Colorings of Graphs without Short Odd Cycles
Motivated by the work of Ne{v{s}}et{v{r}}il and R{"o}dl on ``Partitions of vertices'', we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number $r$ and a graph $G$ of order $m$ with odd
BA - Obecná matematika
- 2011 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Fractional colorings of cubic graphs with large girth
We improve the known upper bounds for the chromatic number of cubic graphs with large girth. In addition, we also improve the lower bound on the independent set and give a simple proof of a weaker upper bound....
BA - Obecná matematika
- 2011 •
- Jx •
- Link
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Výsledek na webu
A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems
In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also in particular that graphs of large girth excluding a ...
IN - Informatika
- 2015 •
- Jx •
- Link
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Výsledek na webu
The last fraction of a fractional conjecture
We complete the prove of the conjecture of Reed on the total fractional colorings of graphs with large girth...
BA - Obecná matematika
- 2010 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Domination number of cubic graphs with large girth
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+ O(n/g)<3n/10 + O(n/g).
BA - Obecná matematika
- 2012 •
- Jx •
- Link
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Výsledek na webu
Coloring squares of planar graphs with girth six
We show that the squares of planar graphs of girth six or more with sufficiently large maximum degree D are (D+2)-colorable.
BA - Obecná matematika
- 2008 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Fractional total colourings of graphs of high girth
We prove that every graph with even maximum degree at least four or with maximum degree three that has a sufficiently large girth has total fractional chromatic number at most the most the maximum degree increased by one which confi...
BA - Obecná matematika
- 2011 •
- Jx •
- Link
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Výsledek na webu
- 1 - 10 out of 58 308