Results 11 to 20 of about 215 (116)
Approximating Vizing's independence number conjecture
, 2019 In 1965, Vizing conjectured that the independence ratio of edge-chromatic critical graphs is at most $\frac{1}{2}$. We prove that for every $\epsilon > 0$ this conjecture is equivalent to its restriction on a specific set of edge-chromatic critical ...
Steffen, Eckhard
core +3 more sources
Vizing's edge-recoloring conjecture holds.
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, 2023 In 1964 Vizing proved that starting from any $k$-edge-coloring of a graph $G$ one can reach, using only Kempe swaps, a $(\Delta+1)$-edge-coloring of $G$ where $\Delta$ is the maximum degree of $G$. One year later he conjectured that one can also reach a $\Delta$-edge-coloring of $G$ if there exists one. Bonamy \textit{et. al} proved that the conjecture
openaire +2 more sources
Inequality Related to Vizing's Conjecture [PDF]
The Electronic Journal of Combinatorics, 2000 Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.
W. Edwin Clark, Stephen Suen
openaire +1 more source
An Improved Inequality Related to Vizing's Conjecture [PDF]
The Electronic Journal of Combinatorics, 2012 Vizing conjectured in 1963 that $\gamma(G \Box H) \geq \gamma(G)\gamma(H)$ for any graphs $G$ and $H$. A graph $G$ is said to satisfy Vizing's conjecture if the conjectured inequality holds for $G$ and any graph $H$. Vizing's conjecture has been proved for $\gamma(G) \le 3$, and it is known to hold for other classes of graphs.
Suen, Stephen, Tarr, Jennifer
openaire +2 more sources
Vizing’s conjecture for chordal graphs
Discrete Mathematics, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Aharoni, Ron, Szabó, Tibor
openaire +2 more sources
Vizing's 2‐Factor Conjecture Involving Large Maximum Degree [PDF]
Journal of Graph Theory, 2017 AbstractLet G be an n‐vertex simple graph, and let and denote the maximum degree and chromatic index of G, respectively. Vizing proved that or . Define G to be Δ‐critical if and for every proper subgraph H of G. In 1965, Vizing conjectured that if G is an n‐vertex Δ‐critical graph, then G has a 2‐factor.
Chen, Guantao, Shan, Songling
openaire +3 more sources
, 2023 Let $γ(G)$ denote the domination number of graph $G$. Let $G$ and $H$ be graphs and $G\Box H$ their Cartesian product. For $h\in V(H)$ define $G_h=\{(g,h)\,|\,g\in V(G)\}$ and call this set a $G$-layer of $G\Box H$. We prove the following special case of Vizing's conjecture. Let $D$ be a dominating set of $G\Box H$.
openaire +2 more sources
An Improved Bound in Vizing’s Conjecture [PDF]
Graphs and Combinatorics, 2019 A well-known conjecture of Vizing is that $ (G \square H) \ge (G) (H)$ for any pair of graphs $G, H$, where $ $ is the domination number and $G \square H$ is the Cartesian product of $G$ and $H$. Suen and Tarr, improving a result of Clark and Suen, showed $ (G \square H) \ge \frac{1}{2} (G) (H) + \frac{1}{2}\min( (G), (H))$.
openaire +3 more sources
Fair reception and Vizing's conjecture
Journal of Graph Theory, 2009 AbstractIn this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable ...
Brešar, Boštjan, Rall, Douglas F.
openaire +3 more sources
Edge-colourings of graphs [PDF]
, 1984 All the results in this thesis are concerned with the classification of graphs by their chromatic class. We first extend earlier results of Fiorini and others to give a complete list of critical graphs of order at most ten.
Chetwynd, Amanda Gillian
core +1 more source