Search

Abstract  A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x 1,x 2, …, x k ,y 1,y 2, …, y k , G contains k pairwise disjoint paths P 1, …, P k such that P i joins x i and y i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P 1, …, P k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. [ABSTRACT FROM AUTHOR]

A weightingwof the edges of a graphGinduces a colouring of the vertices ofGwhere the colour of vertexv, denotedcv, is$$ {\sum\nolimits_{e \mathrel\backepsilon v} {w{\left( e \right)}} } $$. We show that the edges of every graph that does not contain a component isomorphic toK2can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring ofG, for every edge (u,v) ofG,cu?cv. [ABSTRACT FROM AUTHOR]

Ohba has conjectured [7] that if G has 2 ?( G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 ?( G)+1 by $$ \frac{5} {3}\chi {\left( G \right)} - \frac{4} {3}. $$ [ABSTRACT FROM AUTHOR]