Displaying similar documents to “Comparing Imperfection Ratio and Imperfection Index for Graph Classes”

On the number of dissimilar pfaffian orientations of graphs

Marcelo H. de Carvalho, Cláudio L. Lucchesi, U. S.R. Murty (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A subgraph of a graph is if has a perfect matching. An orientation of is if, for every conformal even circuit , the number of edges of whose directions in  agree with any prescribed sense of orientation of is odd. A graph is if it has a Pfaffian orientation. Not every graph is Pfaffian. However, if has a Pfaffian orientation , then the determinant of the adjacency matrix of is the square of the number of perfect matchings of . (See the book by Lovász and Plummer [. Annals...

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let  be the graph obtained from a given graph  by subdividing each edge  times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs  with  edges that are Ramsey with respect to  .

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all   . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all   . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.